fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define f1(i, n) for(ll i=1;i<=n;++i)
  3. #define f0(i, n) for(ll i=0;i<n;++i)
  4. #define ull unsigned long long
  5. #define ll long long
  6. #define rev(a) reverse(a.begin(),a.end())
  7. #define all(x) x.begin(),x.end()
  8. #define so(A, n) sort(A+1, A+n+1)
  9. using namespace std;
  10. const int N = 1e6;
  11. bool checkPrime(int n) {
  12.     if (n == 0 || n == 1) return false;
  13.     for (int i = 2; i <= sqrt(n); ++i) if (n % i == 0) return false;
  14.     return true;
  15. }
  16. vector<int> prime;
  17. int pre[N + 5];
  18. bool mark[N + 5], isPrime[N + 5];
  19. void sieve() {
  20.     fill(isPrime, isPrime + N, true);
  21.     isPrime[0] = isPrime[1] = false;
  22.     for (int i = 2; i * i < N; ++i) {
  23.         if (isPrime[i]) {
  24.             for (int j = i * i; j < N; j += i)
  25.                 isPrime[j] = false;
  26.         }
  27.     }
  28.     for (int i = 2; i < N; ++i) {
  29.         if (isPrime[i]) prime.push_back(i);
  30.     }
  31. }
  32. int main()
  33. {
  34.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  35.     sieve();
  36.     int cnt = 0;
  37.     for (int i = 0; i < prime.size(); ++i) {
  38.         for (int j = i; j < prime.size(); ++j) {
  39.             ll motcaigiday = 1ll * prime[i] * prime[j];
  40.             if (motcaigiday <= N) {
  41.                 mark[motcaigiday] = true;
  42.             }
  43.             else{
  44.                 break;
  45.             }
  46.         }
  47.     }
  48.     pre[0] = 0;
  49.     for (int i = 1; i <= N; ++i) {
  50.         if (mark[i]) {
  51.             pre[i] = pre[i - 1] + 1;
  52.         }
  53.         else {
  54.             pre[i] = pre[i - 1];
  55.         }
  56.     }
  57.     int t;
  58.     cin >> t;
  59.     int a, b;
  60.     while (t--) {
  61.         cin >> a >> b;
  62.         cout << pre[b] - pre[a - 1] << endl;
  63.     }
  64.  
  65.  
  66.  
  67.  
  68.  
  69. }
  70. /*
  71.  
  72.  
  73. */
Success #stdin #stdout 0.01s 9704KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/nTzMZl
language:
C++14 (gcc 8.3)
created:
3 days 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!