fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define FOR(i, a, b) for(int i = (a); i <= (b); i++)
  3.  
  4. using namespace std;
  5. const int N = (int)1e6, MAX = (int)1e6;
  6. bool F[N+10];
  7. int S[N+10], d[N+10];
  8. int n, x, L, R, Q;
  9.  
  10. void Sieve(){
  11.    F[0] = F[1] = 1;
  12.    for(int i = 2; i*i <= MAX; i++)
  13.      if (!F[i])
  14.       for(int j = i*i; j <= MAX; j += i) F[j] = 1;
  15.  
  16.  
  17.    FOR(i, 2, MAX)
  18.     if (!F[i])
  19.       for(int j = i; j <= MAX; j += i) S[i] += d[j];
  20.    FOR(i, 1, MAX) S[i] += S[i-1];
  21. }
  22.  
  23. signed main()
  24. {
  25.     ios_base::sync_with_stdio(false);
  26.     cin.tie(NULL);    cout.tie(NULL);
  27.     freopen("PRIME.inp", "r", stdin);
  28.     freopen("PRIME.out", "w", stdout);
  29.     cin>>n;
  30.     FOR(i, 1, n){
  31.        cin>>x;
  32.        d[x]++;
  33.     }
  34.     Sieve();
  35.     cin>>Q;
  36.     while(Q--){
  37.         cin>>L>>R;
  38.         L = min(L, MAX);
  39.         R = min(R, MAX);
  40.         cout<<S[R]-S[L-1]<<'\n';
  41.     }
  42.     return 0;
  43. }
  44.  
  45.  
Success #stdin #stdout 0.01s 8740KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ihpZpV
language:
C++14 (clang 8.0)
created:
5 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!