【题意】:给出一个L和R,L和R最大差值为100W,问区间[L,R]内相邻的素数最大差值和最小差值分别为多少。(1<=L<R<=2,147,483,647)

【题解】:这题好经典,当年新生赛也出了这题,不过做不出,直到今天终于给我做出来了。
               这题需要知道一个定理,就是对于每一个合数a,其必定存在小于等于根号a的质因子。
               所以对于一个数a我们只需要检查他有没有小于等于根号a的质因子即可。
               考虑到根号2,147,483,647大约是47000,所以我们先筛选出47000以内的素数,大约5000个。
               然后再用这5000个素数去筛选给定区间内的素数。
               最后枚举一次求答案即可。

【代码】:
 1 #include "iostream"
 2 #include "cstdio"
 3 #include "cstring"
 4 #include "algorithm"
 5 #include "vector"
 6 #include "queue"
 7 #include "cmath"
 8 #include "string"
 9 #include "cctype"
10 #include "map"
11 #include "iomanip"
12 using namespace std;
13 #define pb push_back
14 #define lc(x) (x << 1)
15 #define rc(x) (x << 1 | 1)
16 #define lowbit(x) (x & (-x))
17 #define ll long long
18 #define MAX 1000050
19 ll prime[5500], rec[MAX];
20 int tot, cnt;
21 bool isprime[MAX];
22 ll l, r;
23 void init() {
24     tot = 0;
25     memset(isprime, truesizeof(isprime));
26     prime[tot++] = 2;
27     for(int i = 3; i < 50000; i += 2) {
28         if(isprime[i]) {
29             prime[tot++] = i;
30             if(i * i < 50000) {
31                 for(int j = i + i; j < 50000; j += i) isprime[j] = false;
32             }
33         } 
34     }
35 }
36 
37 int main() {
38     init();
39     while(~scanf("%lld%lld", &l, &r)) {
40         if(l < 2) l = 2;
41         cnt = 0;
42         memset(isprime, truesizeof(isprime));
43         for(int i = 0; i < tot && prime[i] * prime[i] <= r; i++) {
44             ll tmp = l / prime[i] * prime[i];
45             if(tmp < l) tmp += prime[i];
46             if(tmp == prime[i]) tmp += prime[i];
47             for(ll j = tmp; j <= r; j += prime[i]) isprime[j-l] = false;
48         }
49         for(int i = 0; i <= r - l; i++) 
50             if(isprime[i]) rec[cnt++] = i + l;
51 
52         if(cnt < 2) printf("There are no adjacent primes.\n");
53         else {
54             int idx1 = 1, idx2 = 1;
55             for(int i = 1; i < cnt; i++) {
56                 if(rec[i] - rec[i-1] < rec[idx1] - rec[idx1-1]) idx1 = i;
57                 if(rec[i] - rec[i-1] > rec[idx2] - rec[idx2-1]) idx2 = i;
58             }
59             printf("%lld,%lld are closest, %lld,%lld are most distant.\n", rec[idx1-1], rec[idx1], rec[idx2-1], rec[idx2]);
60         }
61     }
62     return 0;
63 }
64