fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. #define nl "\n"
  6. #define vi vector<int>
  7. #define all(v) v.begin(), v.end()
  8. #define SORT(v) sort(all(v))
  9. #define SORTX(v) sort(v.begin(), v.end(), greater<int>())
  10. #define read(a) for (auto &i : a) cin >> i
  11. #define Printv(a) for (auto &i : a) cout << i << " "
  12. #define pii pair<int, int>
  13. #define M_ShahaT ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  14.  
  15.  
  16. void FIO(){
  17. #ifndef ONLINE_JUDGE
  18.     freopen("Input.txt","r",stdin);
  19.     freopen("Output.txt","w",stdout);
  20. #endif
  21. }
  22. int dx[] = {1, 0, -1, 0, -1, -1, 1, 1};
  23. int dy[] = {0, -1, 0, 1, -1, 1, -1, 1};
  24. char di[] = {'D', 'L', 'U', 'R'};
  25. double const PI=acos(-1);
  26. const ll INF = 1e18;
  27. const ll mod=1e9+7;
  28. const int N = 2e6 + 5;
  29. int f_1_to_n(int n){
  30.     return n*(n+1)/2;
  31. }
  32. bool valid(int x,int y,int row ,int col){
  33.     return x<row&&x>=0&&y<col&&y>=0;
  34. }
  35.  
  36.  
  37.  
  38.  
  39.  
  40.  
  41.  
  42. vector<bool>vis(N);
  43.         vector<int>prime;
  44. void sieve(){
  45.     for(int i=2;i<N;i++){
  46. if(!vis[i]){
  47.     prime.push_back(i);
  48. for(int j = i;j<=N;j+=i){
  49.     vis[j]=true;
  50. }
  51. }
  52. }
  53. }
  54.  
  55. vector<int>pre;
  56.  
  57.  
  58.  
  59. int binary(int n){
  60.  
  61.         return lower_bound(prime.begin(), prime.end(), n) - prime.begin();
  62.  
  63. }
  64.  
  65.  
  66.  
  67.  
  68.  
  69. void solve_case() {
  70. int a,b;cin>>a>>b;
  71. int inda= binary(a);
  72. int indb= binary(b);
  73.         cout << pre[indb] - pre[inda - 1];
  74. }
  75.  
  76.  
  77.  
  78.  
  79.  
  80.  
  81.  
  82.  
  83.  
  84.  
  85.  
  86.  
  87.  
  88.  
  89.  
  90.  
  91.  
  92. int main(){
  93.     M_ShahaT
  94.     FIO();
  95.  
  96.     int t=1;
  97. sieve();
  98. pre.assign(prime.size(),0);
  99.     for(int i=3;i<prime.size();i++){
  100. if(abs(prime[i-3]-prime[i-2])==2 && abs(prime[i]-prime[i-1])==4){
  101.     pre[i]=pre[i-1]+1;
  102. }else if(abs(prime[i-3]-prime[i-2])==4 && abs(prime[i]-prime[i-1])==2){
  103.     pre[i]=pre[i-1]+1;
  104. }else {
  105. pre[i]=pre[i-1];
  106. }
  107.     }
  108. cin >> t;
  109.     for(int i=1;i<=t;i++){
  110.  
  111.         solve_case();
  112.         cout<<nl;
  113.     }
  114.     return 0;
  115. }
Success #stdin #stdout 0.03s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-356
https://ideone.com/nTVZpV
language:
C++ (gcc 8.3)
created:
18 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!