【题意】：给出一个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, true, sizeof(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, true, sizeof(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