洛谷 P1865 A % B Problem

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<algorithm>
 5 
 6 using namespace std;
 7 
 8 int prime[1000005],is_prime[1000005],ans[1000005];
 9 //int tree[1000005];
10 int n,m,cnt;
11 
12 inline void ou_shai(int x)
13 {
14     for(int i=2;i<=x;i++)
15     {
16         if(is_prime[i]==0) is_prime[i]=i,prime[++cnt]=i;
17         ans[i]=cnt;
18         for(int j=1;j<=cnt;j++)
19         {
20             if(prime[j]*i>x||prime[j]>is_prime[i]) break;
21             is_prime[prime[j]*i]=prime[j];
22         }
23     }
24 }
25 
26 int main()
27 {
28     scanf("%d%d",&n,&m);
29     ou_shai(m);
30     for(int i=1;i<=n;i++)
31     {
32         int x,y;
33         scanf("%d%d",&x,&y);
34         if(y>m||y<1||x<1||x>m)
35         {
36             printf("Crossing the line\n");
37             continue;
38         }
39         if(x<=1) printf("%d\n",ans[y]);
40         else if(is_prime[x]==x) printf("%d\n",ans[y]-ans[x]+1);
41         else  printf("%d\n",ans[y]-ans[x]);
42     }
43     return 0;
44 }