这题真是考验码力的一题。
以前学习的朴素筛,埃氏筛和线性筛都是要从2开始筛的。
这题我们要在任意一个区间筛,前面的方法都失效了。
下面我们学习二次筛法,核心思想是每个合数必然存在一个小于等于sqrt(n)的因子。如果这个因子又是合数,那必然存在小于自己的质因子。所以每个合数必然存在一个小于等于sqrt(n)的质因子。我们先用线性筛把50000之内的质数都筛出来,这些质数就能筛掉任意区间的合数,用埃氏筛。由于筛两次所以叫二次筛法。
为什么第一次筛完,不能用线性筛去筛区间呢?因为线性筛是保证每一个合数被自己最小的质因子筛掉,比如说8是被2筛掉的,但是在外层循环到4的时候才筛掉,而不是在外层循环2的时候筛掉,外层循环2的时候只能筛到4。这里是理解线性筛的关键啊。所以如果区间是从5开始,那就错过了筛掉8的4。只能用埃氏筛。
然后这题很多坑。
要把[l,r]map到[0, r-l],然后我们用第一步的primes翻倍去筛,注意翻倍的时候会暴int,注意要一把取到离l最近的倍数,而且要从2倍primes取起才是合数。还要注意防止1被算成质数的情况。
#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
#define INF 0x3f3f3f3f
const int MOD = 1e9+7;
typedef pair<int, int> PII;
const int N = 50000;
const int M = 1000010;
int l, r;
int vec[M];
int primes[N], cnt, st[N];
void solve(int n) {
for (int i = 2; i <= n; i++) {
if (!st[i]) {
primes[cnt++] = i;
}
for (int j = 0; primes[j] <= n / i; j++) {
st[primes[j] * i] = 1;
if (i % primes[j] == 0)
break;
}
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
solve(N-1);
while (true) {
memset(vec, 0, sizeof vec);
cin >> l >> r;
if (l == 0 && r == 0)
return 0;
for (int i = 0; i < cnt; i++) {
int start = l / primes[i] * primes[i];
for (LL j = start; j <= r; j += primes[i]) {
if (j < l || j == primes[i])
continue;
vec[j-l] = 1;
}
}
if (l == 1)
vec[0] = 1;
int last = -1;
int maxV = 0, minV = INF;
int x1, y1, x2, y2;
for (int i = 0; i <= r - l; i++) {
if (!vec[i]) {
if (last == -1) {
last = i + l;
} else {
int diff = i + l - last;
if (diff > maxV) {
maxV = diff;
x1 = last;
y1 = i+l;
}
if (diff < minV) {
minV = diff;
x2 = last;
y2 = i+l;
}
last = i + l;
}
}
}
if (maxV == 0) {
cout << "There are no adjacent primes." << endl;
} else {
cout << x2 << "," << y2 << " are closest, " << x1 << "," << y1 << " are most distant." << endl;
}
l = r = 0;
}
return 0;
}