C++素数距离
素数距离
质因数组成的基础元素即为质数值，在数学领域内被称为质数值。其中最小者即为2，在随后的一系列自然数字中，3、5、7等均属于此类特殊的数值类型。值得注意的是，在较大的数字范围内，这类特殊数值出现的概率相对较低。
相邻的两个素数组成的概念指的是这两个数字均为质数值的情形，并且在这两个数字之间的区间内不存在其他质数值存在的情况。举例来说, 数字2和3不仅被视为一对相邻质数组成的例子, 同时它们也是连续的整数值序列中的成员。
设计一个算法，在给定区间[L, U]内的整数范围里寻找一对最近邻质数值A与B（其间隔最小化为min(B - A)），同时寻找另一组质数值C与D以最大化它们之间的间距(max(D - C))。当存在多组满足上述条件的情况时，则优先选择最先出现的那一组；满足条件的所有整数值均需满足以下约束：1≤ L < R ≤ 2^31-1且 L ≤ A < B ≤ R、 L ≤ C < D ≤ R
由多个测试用例构成的数据集每一行均对应一个测试用例包括两个正整数参数L和R满足条件的两个参数其差值不得超过1,000,00
给定任意整数区间L到R，请打印出该区间内距离最近的两个连续素数值及其对应的最小间距，并打印出距离最远的两个连续素数值及其对应的间距值。若该区间内没有至少一对连续的素数值存在，则应输出：“该区间中不存在相邻的质数值。”
耗时限制
耗时限制
耗时限制
枚举
那该怎么办呢？
我再次审阅了题目，在脑海中突然浮现了老师曾介绍的一种素数筛选方法。埃式筛法即为这种经典算法的简称。埃拉托斯特尼筛法是由古希腊数学家埃拉托斯特尼提出的一种筛选质数的方法。该算法的基本思想是：通过逐一排除质数的所有倍数来确定质数的过程。具体而言，则是以效率较高的形式对这些倍数值进行标记处理。经过这一系列操作后，在剩余未被标记的数字中筛选出所有的质数值即为此算法的核心内容。通过这一策略能够有效减少不必要的计算过程从而显著提升算法的时间效率其时间复杂度约为O(n log n)这一性能使其在处理较大范围数据时表现出了色成为解析素数组成的有效工具之一以下是我的核心代码实现：
#include<cstdio>
using namespace std;
const int N=1e7+5;
int n;
bool del[N];
bool solve(int n){
for(int i=2;i*i<=n;i++){
if(!del[i]){
for(int j=i;j<=n/i;j++)
del[i*j]=true;
}
}
}
int main()
{
scanf("%d",&n);
solve(n);
for(int i=2;i<=n;i++){
if(!del[i])printf("%d\n",i);
}
return 0;
}知道了爱是筛法后，我们就可以写出如下方案。
方案二：埃式筛法。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=46340,M=1000005;
int l,r,n,pri[N];
bool del[N]={0},f[M]={0};
void init(){
for(int i=2;i*i<=N;i++){
if(!del[i]){
for(int j=i;j<=n/i;j+=i){
del[i*j]=true;
}
}
}
for(int i=2;i<=N;i++){
if(!del[i])pri[++n]=i;
}
}
int main()
{
init();
while(scanf("%d %d",&l,&r)==2){
memset(f,0,sizeof(f));
if(l==1)l=2;
for(int i=1;i<=n;i++){
for(int j=ceil((double)l/pri[i]);j<=r/pri[i];j++){
if(j>1)f[pri[i]*j-1]=true;
}
}
int a,b,c,d,pre=0,maxd=0,mind=1E6+5;
for(int i=l;i<=r;i++){
if(!f[i-1]){
if(pre){
int t=i-pre;
if(t<mind){
mind=t;
a=pre;
b=i;
}
if(t>maxd){
maxd=t;
c=pre;
d=i;
}
}
pre=i;
}
}
if(maxd){
printf("%d,%d are closest, %d,%d are most distant.\n",a,b,c,d);
}
else {
printf("There are no adjacent primes.\n");
}
}
}当我在评测时发现代码仍存在5个错误（导致50分的扣分）。意识到for循环必须从头开始运行才能避免越界问题后, 重新编写并提交了修改后的代码, 经过多次调试和验证终于成功通过测试.
#include<bits/stdc++.h>
using namespace std;
const int N=46340,M=1000005;
int l,r,n,pri[N];
bool del[N]={0},f[M]={0};
void init(){
for(int i=2;i*i<=N;i++){
if(!del[i]){
for(int j=i;j<=n/i;j+=i){
del[i*j]=true;
}
}
}
for(int i=2;i<=N;i++){
if(!del[i])pri[++n]=i;
}
}
int main()
{
init();
while(scanf("%d %d",&l,&r)==2){
memset(f,0,sizeof(f));
if(l==1)l=2;
for(int i=1;i<=n;i++){
for(int j=ceil((double)l/pri[i]);j<=r/pri[i];j++){
if(j>1)f[pri[i]*j-l]=true;
}
}
int a,b,c,d,pre=0,maxd=0,mind=1E6+5;
for(int i=0;i<=r-l;i++){
if(!f[i]){
if(pre){
int t=l+i-pre;
if(t<mind){
mind=t;
a=pre;
b=l+i;
}
if(t>maxd){
maxd=t;
c=pre;
d=l+i;
}
}
pre=l+i;
}
}
if(maxd){
printf("%d,%d are closest, %d,%d are most distant.\n",a,b,c,d);
}
else {
printf("There are no adjacent primes.\n");
}
}
}这可真是一道刺激的题目！！！