AcWing 196. 质数距离
原题链接
中等
作者:
Tizzi
,
2019-11-06 18:29:12
,
所有人可见
,
阅读 790
C++ 代码
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;
const int M = 5e5, N = 1e6 + 5;
int pri[M + 5], cnt, newpri[N];
ll L, R;
bool v[N + 5];
void primes(int n) {
for (int i = 2; i <= n; i++) {
if (!v[i]) pri[cnt++] = i;
for (int j = 0; pri[j] <= n / i; j++) {
v[i * pri[j]] = true; //标记为质数
if (i % pri[j] == 0) break;
}
}
}
int main() {
primes(50000);
while (scanf("%lld%lld", &L, &R) != EOF) {
memset(v, false, sizeof(v));
for (int j = 0; j < cnt; j++) {
ll p = pri[j];
//通过2~根号R的质数 筛出 L~R范围内的 不能将自己本身包括进去
for (ll j = max((L + p - 1) / p * p, 2 * p); j <= R; j += p) {
//进行离散化 全部偏移L
v[j - L] = true;
}
}
int num = 0;
//1 这个条件要特判断 因为当L == 1的时候
for (int i = 0; i <= R - L; i++) {
if (!v[i] && i + L != 1) newpri[num++] = i + L;
}
if (num < 2) {
printf("There are no adjacent primes.\n");
} else {
//找出最大最小
int minid = 0, maxid = 0;
for (int i = 1; i < num - 1; i++) {
int d = newpri[i + 1] - newpri[i];
int lamin = newpri[minid + 1] - newpri[minid];
int lamax = newpri[maxid + 1] - newpri[maxid];
if (d > lamax) maxid = i;
if (d < lamin) minid = i;
}
printf("%d,%d are closest, %d,%d are most distant.\n", newpri[minid] , newpri[minid + 1], newpri[maxid], newpri[maxid + 1]);
}
}
return 0;
}