质数——质数距离
发布时间
阅读量：
阅读量
质数距离
设定整数L和U，在闭区间[L, U]内寻找距离最近的一对相邻质数C₁和C₂（其中C₂ - C₁最小），若有多个满足条件的情况出现，则应优先输出最先出现的情况。
此外,你需要寻找距离最远的一对相邻质数D₁和D₂（其中,D₁ - D₂是最大值）,若存在间距相同的另一对相邻质数,则输出最先出现的那一组.
输入格式
每行输入两个整数L和U，其中L和U的差值不会超过1000000。
输出格式
对于每个L和U ，输出一个结果，结果占一行。
结果涵盖包括两个方面：一是距离最近的相邻质数对；二是距离最远的相邻质数对。（具体格式请参考样例）
如果L和U之间不存在质数对，则输出“There are no adjacent primes.”。
数据范围中L与U满足关系条件：其中L和U满足 1 \leq L < U \leq 2^{31}-1 的关系。
输入数据包括两个案例：
第一组为数值对（2, 17）；
第二组为数值对（14, 17）。
输出结果包括两部分：
第一部分展示了最近的素数对（closest）；
第二部分展示了最远的素数对（most distant）。
此外还指出没有相邻的素数存在。
题解：
通过区间偏移进行大区间质数筛选。这相当于计算(l + p - 1) / p的结果。从而确定了不小于l的第一个倍数位置。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1000010;
int primes[N], cnt;
bool st[N];
void init(int n)
{
memset(st, 0, sizeof st);
cnt = 0;
for (int i = 2; i <= n; i ++ ){
if (!st[i]) primes[cnt ++ ] = i;
for (int j = 0; primes[j] * i <= n; j ++ ){
st[i * primes[j]] = true;
if (i % primes[j] == 0) break;
}
}
}
int main()
{
int l, r;
while (cin >> l >> r){
init(50000);
memset(st, 0, sizeof st);
for (int i = 0; i < cnt; i ++ ){
LL p = primes[i];
for (LL j = max(p * 2, (l + p - 1) / p * p); j <= r; j += p)
st[j - l] = true;
}
cnt = 0;
for (int i = 0; i <= r - l; i ++ )
if (!st[i] && i + l >= 2)
primes[cnt ++ ] = i + l;
if (cnt < 2) puts("There are no adjacent primes.");
else{
int minp = 0, maxp = 0;
for (int i = 0; i + 1 < cnt; i ++ ){
int d = primes[i + 1] - primes[i];
if (d < primes[minp + 1] - primes[minp]) minp = i;
if (d > primes[maxp + 1] - primes[maxp]) maxp = i;
}
printf("%d,%d are closest, %d,%d are most distant.\n",
primes[minp], primes[minp + 1],
primes[maxp], primes[maxp + 1]);
}
}
return 0;
}全部评论 (0)
还没有任何评论哟~