Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
线形筛+普通筛#include <iostream> #include <cstring> #include <cstdio> #include <bitset> using namespace std; const int MAXN=65535; const int INF=1000050; long long l,r; long long a,b,c,d,e,f; long long prim[MAXN],num; bitset<INF> v; void prime() { v.reset(); for(int i=2;i<=MAXN;i++) { if(!v[i])prim[++num]=i; for(int j=1;j<=num;j++) { if(i*prim[j]>MAXN)break; v[i*prim[j]]=1; if(i%prim[j]==0)break; } } }//线形筛 void get_prime() { v.set(); for(long long i=1;i<=num;i++) for(long long j=r/prim[i];j>1&&prim[i]*j>=l;j--)v[prim[i]*j-l]=false; }//普通筛 int main() { prime(); while(cin>>l>>r) { if(l==1)l=2; get_prime(); a=-1000000,b=1000000,c=0,d=0,e=0,f=0; for(long long i=l;i<=r;i++) { if(v[i-l]) { e=f;f=i; if(e>0) { if(f-e<b-a)b=f,a=e; if(f-e>d-c)d=f,c=e; } } } if(a<0)puts("There are no adjacent primes."); else printf("%lld,%lld are closest, %lld,%lld are most distant.\n",a,b,c,d); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator