首页 > 代码库 > POJ 2689

POJ 2689

2024-07-19 22:01:30   216人阅读

YEAH DONG DONG

终于过了。

这样思考，首先，要把所有素数求出来是不可能的。注意到L,R的差仅一百万，那么就可以只求这个范围内的素数了。而筛选范围内的素数，就可以用上一篇的方法，使用若n为合数，则必有素因子在sqrt(n)中。

在筛选范围内的素数2了一次，直接判断每个数是否素数,TLE。。。

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace std;const int LPR=50000;const int Cprime=1000000;const int inf=(1<<30);bool isprime[LPR+10];bool gsprime[Cprime+10];__int64 prime[LPR],cp;__int64 gprime[Cprime+10],gp;void Isprime(){	memset(isprime,true,sizeof(isprime));	int e=(int)sqrt(LPR*1.0);	isprime[0]=isprime[1]=false;	for(int i=2;i<=e;i++){		if(isprime[i]){			for(int j=i*i;j<=LPR;j+=i)			isprime[j]=false;		}	}}void Doprime(){	cp=0;	for(int i=1;i<=LPR;i++)	if(isprime[i])	prime[cp++]=i;}/*void Fprime(__int64 tp){	for(__int64 i=0;prime[i]*prime[i]<=tp;i++){		if(tp%prime[i]==0) return ;	}	gprime[gp++]=tp;}*/void Fprime(__int64 L,__int64 R){	memset(gsprime,true,sizeof(gsprime));	__int64 tp=L;	if(L==1){		gsprime[0]=false;		L++;	}	for(__int64 i=0;i<cp;i++){		if(prime[i]>R) break;		__int64 s=L/prime[i];		if(s*prime[i]<L)		s++;		bool flag=false;		for(__int64 p=s*prime[i];p<=R;p+=prime[i]){			if(s==1&&!flag){				flag=true;				continue;			}			gsprime[p-tp]=false;		}	}	for(__int64 i=0;i<=R-tp;i++)	if(gsprime[i])	gprime[gp++]=i+tp;}int main(){	__int64 L,R; __int64 mind,maxd; __int64 mil,mir,mal,mar;	Isprime();	Doprime();//	cout<<prime[0]<<prime[1]<<prime[2]<<prime[3]<<endl;	while(scanf("%I64d%I64d",&L,&R)!=EOF){	//	cout<<L<<‘ ‘<<R<<endl;		mind=inf; maxd=0;		gp=0;	/*	for(__int64 i=L;i<=R;i++){			if(i==2){ gprime[gp++]=i; continue; }			if(i%2==0) continue;			Fprime(i);		}*/		Fprime(L,R);		if(gp==0||gp==1)		printf("There are no adjacent primes.\n");		else {			for(int i=0;i<gp-1;i++){				if(gprime[i+1]-gprime[i]<mind){					mind=gprime[i+1]-gprime[i];					mil=gprime[i]; mir=gprime[i+1];				}				if(gprime[i+1]-gprime[i]>maxd){					maxd=gprime[i+1]-gprime[i];					mal=gprime[i]; mar=gprime[i+1];				}			}			printf("%I64d,%I64d are closest, %I64d,%I64d are most distant.\n",mil,mir,mal,mar);		}	}	return 0;}

　　

POJ 2689


联系
我们