当前位置：首页 > news >正文

poj 2689 Prime Distance （素数二次筛法）

news 来源：原创 2024/5/16 9:16:23

2689 -- Prime Distance

　　没怎么研究过数论，还是今天才知道有素数二次筛法这样的东西。

　　题意是，要求求出给定区间内相邻两个素数的最大和最小差。

　　二次筛法的意思其实就是先将1~sqrt(b)内的素数先筛出来，然后再对[a,b]区间用那些筛出来的素数再次线性筛。

代码如下：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <iostream>
 5 
 6 using namespace std;
 7 
 8 const int N = 66666;
 9 int prm[N >> 3], pn;
10 bool np[N];
11 
12 void getbase() {
13     np[pn = 0] = np[1] = true;
14     prm[pn++] = 2;
15     for (int i = 3; i < N; i++, i++) {
16         if (!np[i]) prm[pn++] = i;
17         for (int j = 0, tmp; j < pn; j++) {
18             tmp = i * prm[j];
19             if (tmp >= N) break;
20             np[tmp] = true;
21             if (i % prm[j] == 0) break;
22         }
23     }
24 //    cout << pn << endl;
25 //    for (int i = 0; i < 10; i++) cout << prm[i] << endl;
26 }
27 
28 bool mk[1111111];
29 
30 int main() {
31 //    freopen("in", "r", stdin);
32     getbase();
33     int T;
34     long long a, b;
35     while (~scanf("%lld%lld", &a, &b)) {
36         a = max(2ll, a);
37         memset(mk, 0, sizeof(mk));
38         for (int i = 0; i < pn && prm[i] <= b; i++) {
39             long long t = a / prm[i] * prm[i];
40             if (t != a) t += prm[i];
41             t = max(t, (long long) prm[i] << 1);
42             for ( ; t <= b; t += prm[i]) mk[t - a] = true;
43         }
44         long long p = a;
45         int mini = 1111111, maxi = -1111111, minp, maxp;
46         while (p <= b && mk[p - a]) p++;
47         for (long long i = p + 1; i <= b; i++) {
48             if (mk[i - a]) continue;
49 //            cout << i << endl;
50             if (maxi < i - p) maxi = i - p, maxp = p;
51             if (mini > i - p) mini = i - p, minp = p;
52             p = i;
53         }
54         if (maxi < 0) puts("There are no adjacent primes.");
55         else printf("%d,%d are closest, %d,%d are most distant.\n", minp, minp + mini, maxp, maxp + maxi);
56     }
57     return 0;
58 }