一道二分题。
我们需要用二分在 \(O(n\log n)\) 的时间复杂度内得到答案，也就是说我们的判断函数时间复杂度必须为 \(O(n)\)，因此考虑前缀和。
\(sum_i\) 表示出现在区间 \(\left[a,b \right]\) 内的前 \(i\) 个数中质数的数量。
在二分的判断函数里，我们可以枚举左端点 \(i\)，用 \(sum_{i-1+x} - sum_{i-1}\) 可以得到区间 \(\left[i,i-1+x \right]\) 中质数的数量。其中，\(x\) 为区间长度。
Code
#include <bits/stdc++.h>
#define ll long long
#define INF 1e9
using namespace std;
int a, b, k, ans;
int sum[1000005];
bool removed[1000005];
void init() {
removed[1] = 1;
for (int i = 2; i * i <= b; i++) {
if (!removed[i]) {
for (int j = i * i; j <= b; j += i) removed[j] = 1;
}
}
}
bool check(int x) {
for (int i = a; i - 1 + x <= b; i++) {
if (sum[i - 1 + x] - sum[i - 1] < k) return 0;
}
return 1;
}
void f(int l, int r) {
while (l <= r) {
int mid = (l + r) / 2;
if (check(mid)) {
r = mid - 1;
ans = mid;
}
else l = mid + 1;
}
}
signed main() {
ios :: sync_with_stdio(0);
cin >> a >> b >> k;
init();
for (int i = a; i <= b; i++) {
sum[i] = sum[i - 1];
if (!removed[i]) sum[i]++;
}
f(1, 5000000);
if (ans <= b - a + 1) cout << ans;
else cout << -1;
return 0;
}