Codeforces Round #226 (Div. 2) C题

 2 #include<algorithm>
 3 #include<cstdio>
 4 using namespace std;
 5 const int MAX=10000000+10;
 6 int vis[MAX],sum[MAX],num[MAX];
 7 int main()
 8 {
 9     int a,l,r,n,m;
10     scanf("%d",&n);
11     memset(vis,0,sizeof(vis));
12     memset(sum,0,sizeof(sum));
13     for(int i=0;i<n;i++)
14     {
15         scanf("%d",&a);
16         num[a]++;
17     }
18     for(int i=2;i<MAX;i++)
19     {
20         if(!vis[i])
21         {
22             for(int j=i;j<=MAX;j+=i)
23             {
24                 vis[j]=1;
25                 sum[i]+=num[j];
26             }
27         }
28         sum[i]+=sum[i-1];
29     }
30     scanf("%d",&m);
31     for(int i=0;i<m;i++)
32     {
33         scanf("%d %d",&l,&r);
34         l=min(l,MAX-2);
35         r=min(r,MAX-2);
36         printf("%d\n",sum[r]-sum[l-1]);
37     }
38     return 0;