LightOj 1197 Help Hanzo （区间素数筛选）

题目大意：

　　给出T个实例，T<=200，给出[a,b]区间,问这个区间里面有多少个素数？(1 ≤ a ≤ b < 2³¹, b - a ≤ 100000)

解题思路：

　　由于a，b的取值范围比较大，无法把这个区间内的所以素数全部筛选出来，但是b-a这个区间比较小，所以可以用区间素数筛选的办法解决这个题目。

代码：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<cmath>
 6 using namespace std;
 7 
 8 #define maxn 50000
 9 int vis[maxn], isprime[5200], num[100005], k;
10 void prime()//只需要把[1,sqrt（2^31）]之间的素数筛选出来就ok了。
11 {
12     long long i, j;
13     for (k=0,i=2; i<maxn; i++)
14         if (vis[i] == 0)
15         {
16             isprime[k ++] = i;
17             for (j=i*i; j<maxn; j+=i)
18                 vis[j] = 1;
19         }
20     //printf ("%lld
", k);
21 }
22 
23 int main ()
24 {
25     int t, l = 1;
26     prime ();
27     scanf ("%d", &t);
28     while (t --)
29     {
30         int a, b, ans = 0;
31         int n;
32         scanf ("%d %d", &a, &b);
33         n = b - a;//所求区间最大可达下标
34         memset (num, 0, sizeof(num));
35         for (int i=0; isprime[i]<=(int)sqrt(b)&& i<k; i++)
36         {
37             int j = 0;
38             if (a % isprime[i] != 0 )//第一个需要筛掉的数(j+a) % isprime[i] == 0
39                 j = j - a % isprime[i] + isprime[i];
40             if (a <= isprime[i])//(j+a) / isprime[i] == 1,则(j+a)是素数，要向下推一个
41                 j += isprime[i];
42             for ( ; j<=n; j+=isprime[i])
43             {
44                     num[j] = 1;
45             }
46         }
47         for (int i=0; i<=n; i++)//计算素数的数目
48             if (!num[i])
49             ans ++;
50         if (a == 1)//对这种情况特殊处理
51             ans --;
52         printf ("Case %d: %d
", l ++, ans);
53     }
54     return 0;
55 }

本文为博主原创文章，未经博主允许不得转载。