440
POJ 2689 素數篩法
這道題很講究技巧 不是一般的篩法 一定要充分理解篩法才行 一上來硬做肯定超時 題目給定了兩數的差
就是要把這個區間的素數都給篩出來 那麼先篩出能求出U最大時需要的素數情況 然後通過這些素數再篩
給定區間內的素數 具體看程序 寫的很明白了
#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAX 150000
#define max 1000005
bool isprime[MAX];
long long prime[MAX],nprime;
void getprime() //篩素數
{
long long i,j;
memset(isprime,1,sizeof(isprime));
nprime=0;
isprime[1]=0;
for(i=2; i<MAX; i++)
if(isprime[i])
{
prime[++nprime]=i;
for(j=i*i; j<MAX; j+=i)
isprime[j]=0;
}
}
bool iprime[max];
void pdprime(long long l,long long u)//篩給定區間素數
{
memset(iprime,1,sizeof(iprime));
if(l==1)
iprime[0]=0;
for(int i=1; prime[i]*prime[i]<=u; i++)
{
long long s=prime[i];
for(long long j=(l/s)*s; j<=u; j+=s)
{
if(j-l<0||j==s)
continue;
iprime[j-l]=0;
}
}
}
int main()
{
getprime();
long long l,u;
while(~scanf("%lld%lld",&l,&u))
{
pdprime(l,u);
long long sum=0,dis,maxd=0,mind=9999999,max1,max2,min1,min2,last;
for(int i=0; i<=u-l; i++)
{
if(iprime[i])
{
sum++;
if(sum>=2)
{
dis=i-last;
if(dis<mind)
mind=dis,min1=last+l,min2=i+l;
if(dis>maxd)
maxd=dis,max1=last+l,max2=i+l;
}
last=i;
}
}
if(sum>=2)
printf("%lld,%lld are closest, %lld,%lld are most distant.\n",min1,min2,max1,max2);
else
printf("There are no adjacent primes.\n");
}
return 0;
}
最後更新：2017-04-04 07:03:27