1439 统计素数个数

时间限制: 1 s

空间限制: 1000 KB

题目等级 : 青铜 Bronze

题目描述 Description

输入区间[L, R]，寻找在此区间内的质数。

输入描述 Input Description

开区间[L, R]中的整数L，R

输出描述 Output Description

在此区间中所有质数的个数n

样例输入 Sample Input

0 100

样例输出 Sample Output

数据范围及提示 Data Size & Hint

对于所有数据，L,R<=21000，区间长度R-L<=4000

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<cstring>
 5 using namespace std;
 6 bool vis[1000002];int c,q,ans=0;
 7 void sieve_method()
 8 {
 9     int j,i;
10     for(i=2;i<=sqrt(q+0.5);i++)
11     {
12         if(!vis[i])
13         {
14             for(j=i*i;j<=q;j+=i)
15             vis[j]=1;
16         }
17     }
18     vis[1]=1;
19     vis[0]=1;
20     for(i=c;i<=q;i++)
21     {
22         if(!vis[i])
23         ans++;
24     }
25     cout<<ans;
26 }
27 
28 int main()
29 {
30     scanf("%d%d",&c,&q);
31     sieve_method();
32     return 0;
33 }