素数筛 poj 2689

素数筛

#include<stdio.h>
#include<string.h>
#include<algorithm> using namespace std;
#define MAXN 47000
#define inf 100000000 bool z[MAXN];
int x[MAXN];
bool y[];
int x1[]; int main()
{
int a,b;
for(int i=;i<=;i++) //可以从小的素数开始筛
{
if(!z[i])
for(int j=i*i;j<MAXN;j+=i)
z[j]=;
}
int cnt=;
for(int i=;i<MAXN;i++) //这个范围可以筛出2147483647
if(!z[i])
x[cnt++]=i;
while(scanf("%d%d",&a,&b)!=EOF)
{
int m1=inf,m2=-;
int en=b-a;
memset(y,,sizeof(y));
if(a==)
a++; for(int i=;i<cnt;i++) //b-a<=1000000 从a开始筛
{
int a1,b1;
a1=(a-)/x[i]+;
b1=b/x[i];
for(int j=a1;j<=b1;j++)
if(j>)
y[j*x[i]-a]=;
} int cnt1=; for(int i=;i<=b-a;i++)
if(!y[i])
{
x1[cnt1++]=i+a;
} int i=,j=cnt1-;
while(x1[i]<a)
i++;
while(x1[j]>b&&j>=)
j--;
int l1,r1,l2,r2; for(int k=i;k+<=j;k++)
{
if(x1[k+]-x1[k]>m2)
{
m2=x1[k+]-x1[k];
r2=x1[k+];
l2=x1[k];
}
if(x1[k+]-x1[k]<m1)
{
m1=x1[k+]-x1[k];
r1=x1[k+];
l1=x1[k];
}
}
if(m2==-)
printf("There are no adjacent primes.\n");
else
printf("%d,%d are closest, %d,%d are most distant.\n",l1,r1,l2,r2);
}
return ;
}
上一篇:CentOS yum时出现"Could not retrieve mirrorlist"


下一篇:wireshark 无线抓包