POJ 2689 Prime Distance（素数筛选）

题目链接：http://poj.org/problem?id=2689

题意：给出一个区间[L, R]，找出区间内相连的，距离最近和距离最远的两个素数对。其中(1<=L<R<=2,147,483,647) R - L <= 1000000

思路：数据量太大不能直接筛选，要采用两次素数筛选来解决。我们先筛选出2 - 50000内的所有素数，对于上述范围内的数，如果为合数，则必定有2 - 50000内的质因子。换一句话说，也就是如果一个数没有2 - 50000内的质因子，那么这个数为素数。假设我们先预处理出2 - 50000内的所有素数，只需要从头到尾筛选一遍即可。

code：

 1 #include <cstdio>
 2 #include <cstring>
 3 typedef long long LL;
 4 const int MAXN = 50000;
 5 const int MAXM = 1000005;
 6 int primeA[MAXN];    // primeA[0]存放2-MAXN的素数个数  primeA[i]的值为第i个值
 7 int primeB[MAXM];    // primeB[0]存放L-R的素数个数  primeB[i]的值为区间内第i个素数的值
 8 bool isPrime[MAXM];
 9 
10 // 筛选出MAXN内的所有素数
11 void GetPrimeA()
12 {
13     memset(primeA, 0, sizeof(primeA));
14     for (int i = 2; i < MAXN; ++i)
15     {
16         if (!primeA[i]) primeA[++primeA[0]] = i;
17         for (int j = 1; j <= primeA[0] && primeA[j] * i < MAXN; ++j)
18         {
19             primeA[primeA[j] * i] = 1;
20             if (i % primeA[j] == 0) break;
21         }
22     }
23 }
24 
25 // 利用primeA筛选出primeB
26 void GetPrimeB(int L, int R)
27 {
28     memset(isPrime, true, sizeof(isPrime));
29     if (L < 2) L = 2;
30 
31     // 从第一个素数开始，一直到primeA[0]，筛选出[L, R]内的素数
32     for (int i = 1; i <= primeA[0] && (LL)primeA[i] * primeA[i] <= R; ++i)
33     {
34         int s = L / primeA[i] + (L % primeA[i] > 0);
35         if (s == 1) s = 2;    // 刚好为1，此时要筛选的数为素数
36         for (int j = s; (LL)j * primeA[i] <= R; ++j)
37         {
38             if ((LL)j * primeA[i] >= L)
39                 isPrime[(LL)j * primeA[i] - L] = false;    // j * primeA[i]显然不是素数，他有质因子primeA[i]
40                                                         // 由于数据较大，可以利用相对L的距离来存这个数
41         }
42     }
43     primeB[0] = 0;
44     int len = R - L;
45     for (int i = 0; i <= len; ++i)
46     {
47         if (isPrime[i])
48             primeB[++primeB[0]] = i + L;
49     }
50 }
51 
52 int main()
53 {
54     GetPrimeA();
55     int L, R;
56     while (scanf("%d %d", &L, &R) == 2)
57     {
58         GetPrimeB(L, R);
59         if (primeB[0] < 2)
60         {
61             printf("There are no adjacent primes.
");
62             continue;
63         }
64         int x1 = 0, y1 = 10000000, x2 = 0, y2 = 0;
65         for (int i = 1; i < primeB[0]; ++i)
66         {
67             if (primeB[i + 1] - primeB[i] < y1 - x1)
68             {
69                 x1 = primeB[i];
70                 y1 = primeB[i + 1];
71             }
72             if (primeB[i + 1] - primeB[i] > y2 - x2)
73             {
74                 x2 = primeB[i];
75                 y2 = primeB[i + 1];
76             }
77         }
78         printf("%d,%d are closest, %d,%d are most distant.
", x1, y1, x2, y2);
79     }
80     return 0;
81 }