CDOJ--1550&&1731

原题链接：http://acm.uestc.edu.cn/problems.php?vol=15

分析：首先筛出sqrt(2^31-1)以内的素数，对于给定的区间[L,R],仍然用筛素数的思想把那些是前面筛选出来的素数的倍数的做标记，然后从左到右扫一遍即可。

How many primes

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #define maxn 100005
 6 using namespace std;
 7 int prime[maxn],t;
 8 bool ans[1000005];
 9 bool flag[maxn]={false};
10 void selprime()
11 {
12     t=0;
13     for(int i=2;i<=100000;i++)
14     {
15         if(!flag[i])
16         {
17             prime[t++]=i;
18             for(int j=1;j*i<=100000;j++)
19             flag[i*j]=true;
20         }
21     }
22 }
23 void solve(int m,int n)
24 {
25     for(int i=0;i<t;i++)
26     {
27         if(prime[i]*2>n)break;
28         int j=m/prime[i];
29         if(j*prime[i]<m)j++;
30         j=max(j,2);
31         for(;j*prime[i]<=n;j++)
32         {
33             ans[j*prime[i]-m]=false;
34         }
35     }
36 }
37 int main()
38 {
39     int m,n;
40     selprime();
41     while(~scanf("%d%d",&m,&n))
42     {
43         if(m==1)m++;
44         memset(ans,true,sizeof(ans));
45                     solve(m,n);
46                     int res=0;
47         for(int i=0;i<=n-m;i++)
48         {
49             if(ans[i])res++;
50         }
51         printf("%d
",res);
52     }
53     return 0;
54 }

View Code