筛质数3:质数距离
作者:
总打瞌睡的天天啊
,
2024-08-06 12:09:40
,
所有人可见
,
阅读 1
//这道题要在l~r之间筛质数
//n是和数,一定可以找到它的最小质因子p,p<根号n
//先预处理所有质因子,再筛合数
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1000010;
typedef long long LL;
int prime[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])prime[cnt++]=i;
for(int j=0;i*prime[j]<=n;j++)
{
st[i*prime[j]]=true;
if(i%prime[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=prime[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)
prime[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=prime[i+1]-prime[i];
if(d<prime[minp+1]-prime[minp])minp=i;
if(d>prime[maxp+1]-prime[maxp])maxp=i;
}
printf("%d,%d are closest, %d,%d are most distant.\n",
prime[minp],prime[minp+1],prime[maxp],prime[maxp+1]);
}
}
return 0;
}