fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define PB push_back
  5. #define FI first
  6. #define SE second
  7. #define PI pair<int,int>
  8. #define MP make_pair
  9. #define ALL(DATAST) DATAST.begin(), DATAST.end()
  10. #define MOD 1000000007
  11. #define SIZE 1000000
  12. #define LMT 1000000
  13.  
  14. int sieve[SIZE];
  15. int cnt[SIZE];
  16. int ans[SIZE];
  17.  
  18. int main()
  19. {
  20.     ios::sync_with_stdio(0);
  21.     cin.tie(0); cout.tie(0);
  22. #ifndef ONLINE_JUDGE
  23.     freopen("input.txt", "r", stdin);
  24.     freopen("output.txt", "w", stdout);
  25. #endif
  26.  
  27.  
  28.     for (ll i = 0; i < SIZE; i++)
  29.     {
  30.         cnt[i] = 0;
  31.         sieve[i] = i;
  32.     }
  33.  
  34.     for (ll i = 2; i < SIZE; i++)
  35.     {
  36.         if (sieve[i] == i)
  37.         {
  38.             for (ll j = 2 * i; j < SIZE; j += i)
  39.             {
  40.                 sieve[j] /= i;
  41.                 cnt[j]++;
  42.             }
  43.         }
  44.     }
  45.  
  46.     for (int i = 0; i < SIZE; i++)
  47.         ans[i] = (sieve[i] == 1 && cnt[i] == 2);
  48.  
  49.     for (int i = 1; i < SIZE; i++)
  50.         ans[i] += ans[i - 1];
  51.  
  52.  
  53.  
  54.  
  55.     int t, l, r;
  56.     cin >> t;
  57.  
  58.     while (t--)
  59.     {
  60.         cin >> l >> r;
  61.         cout << ans[r] - ans[l - 1] << endl;
  62.     }
  63.  
  64.  
  65.  
  66.  
  67.     return 0;
  68. }
Success #stdin #stdout 0.05s 15152KB
comments (?)
stdin
copy 
3
1 5
2 10
56 65
stdout
copy 
0
2
4
https://ideone.com/gDVHWB
language:
C++14 (gcc 8.3)
created:
4 years 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!