POJ 2689 Prime Distance(筛法)

题意：求L到R之间的素数距离最小的两个，和距离最大的两个，如果存在几个，则取第一个。(1=<L<R<=2^32)

思路：1、先预处理1到50000的素数（50000^2>2^32）.存入prime[50000]中

2、for(i=0;prime[i]*prime[i]<=R;i++)
{
k=L/prime[i];
j=k*prime[i];
if(k<=1)
j=prime[i]+prime[i];（L<=prime[i]时，如prime[0]=2,L=2;则k=1，j=2，而2是素数故不能筛去，L=1时，k=0，j=0，也不符合）

for(;j<=R;j+=prime[i])
if(j-L>=0)
isprime[j-L]=true;
}

3、代码

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
using namespace std;
#define LL __int64
#define CL(a,b) memset(a,b,sizeof(a))
#define INF 0xfffffff
const int M(50000);
bool is[M],isprime[2000010];
LL prime[M];
void init()
{
	int i,j;
	CL(is,false);
	is[0]=is[1]=true;
	for(i=2;i*i<M;i++)
		if(!is[i])
		{
			for(j=i+i;j<M;j+=i)
				is[j]=true;
		}
	for(i=0,j=0;i<M;i++)
		if(!is[i])
			prime[j++]=i;
//	printf("%d\n",prime[j-1]);
}
void solve(LL L,LL R)
{
	LL i;
	LL j,k,minm,maxm;
	LL x,y,xx,yy,pre;
	CL(isprime,false);
	if(L==1)
		isprime[0]=true;
	for(i=0;prime[i]*prime[i]<=R;i++)
	{
		k=L/prime[i];
		j=k*prime[i];
		if(k<=1)
			j=prime[i]+prime[i];
		for(;j<=R;j+=prime[i])
			if(j-L>=0)
				isprime[j-L]=true;
	}
	minm=INF;
	maxm=0;
	pre=-1;
	x=y=xx=yy=-1;
	for(i=L;i<=R;i++)
		if(!isprime[i-L])
		{
		//	printf("%d ",i);
			if(pre!=-1)
			{
				if(i-pre>maxm)
				{
					maxm=i-pre;
					x=pre;y=i;
				}
				if(i-pre<minm)
				{
					minm=i-pre;
					xx=pre;yy=i;
				}
			}
			pre=i;
		}
//	printf("\n");
	if(x!=-1)
		printf("%I64d,%I64d are closest, %I64d,%I64d are most distant.\n",xx,yy,x,y);
	else
		printf("There are no adjacent primes.\n");
	
}
int main()
{
	LL L,R;
	init();
	while(scanf("%I64d%I64d",&L,&R)!=EOF)
	{
		solve(L,R);
	}
}