题意：求[a, b]之间差最大/小的相邻素数。
0 < a, b < 2^32, 0 < b - a <= 1e6
首先发现a,b很大，以至于无法求出素数来。
然后就考虑退而求次，求出sqrt(b)以内的素数。
发现可以枚举[a, b]之间的数，还开的下一个vis数组。
然后考虑筛去所有合数。
用sqrt(b)以内的素数筛合数即可。
有两个点要注意：
1，b可能等于2147483647，故for循环里面要写成 i <= b && i > 0
2，注意1不是质数，所以a == 1时vis[0] = 1
#include <cstring>
#include <cstdio>
typedef long long LL;
const int N = ;
LL INF = ; int a, b, top, p[N];
bool vis[N]; inline void solve() {
memset(vis, , (b - a + ) * sizeof(bool));
for(int i = ; i <= top && p[i] * p[i] <= b; i++) {
int j = (a / p[i]) * p[i];
if(j < a) {
j += p[i];
}
if(j == p[i]) {
j += p[i];
}
for(; j <= b && j > ; j += p[i]) {
vis[j - a] = ;
}
}
if(a == ) {
vis[] = ;
} int last = ;
int c = , d = ;
for(int i = a; i <= b && i > ; i++) {
if(vis[i - a]) {
continue;
}
if(!d) {
d = i;
}
else if(!c) {
c = d;
d = i;
last = d;
}
else {
if(i - last < d - c) {
c = last;
d = i;
}
last = i;
}
}
if(!c) {
puts("There are no adjacent primes.");
return;
}
printf("%d,%d are closest, ", c, d);
last = c = d = ;
for(int i = a; i <= b && i > ; i++) {
if(vis[i - a]) {
continue;
}
if(!d) {
d = i;
}
else if(!c) {
c = d;
d = i;
last = d;
}
else {
if(i - last > d - c) {
c = last;
d = i;
}
last = i;
}
}
printf("%d,%d are most distant.\n", c, d);
return;
} inline void getp() {
for(int i = ; 1ll * i * i <= INF; i++) {
if(!vis[i]) {
p[++top] = i;
}
for(int j = ; j <= top && 1ll * i * p[j] * i * p[j] <= INF; j++) {
vis[i * p[j]] = ;
if(i % p[j] == ) {
break;
}
}
}
return;
} int main() {
getp();
while(scanf("%d%d", &a, &b) != EOF) {
solve();
} return ;
}
AC代码