| ||||||||||
| 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