【題意】：給出一個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