| ||||||||||
| 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 | |||||||||
对拍了两千组范围内的随机数据都过了 包括discuss里的,还是wa...,哪位大佬给看看吖#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long ll;
const int maxn=100000;
int prime[maxn],v[maxn],m;
bool nt_prime[10*maxn+5];
ll tmp[maxn*10+5];
void primes(int n)
{
for(int i=2;i<=n;i++)
{
if(v[i]==0)
{
prime[++m]=i;
v[i]=i;
}
for(int j=1;j<=m;j++)
{
if(prime[j]>v[i]||prime[j]>n/i)break;
v[prime[j]*i]=prime[j];
}
}
}
int main()
{
//freopen("E:\\duipai\\in.txt","r",stdin);
//freopen("E:\\duipai\\out.txt","w",stdout);
ll l,r;
while(~scanf("%lld%lld",&l,&r)){
m=0;
memset(v,0,sizeof(v));
memset(prime,0,sizeof(prime));
memset(tmp,0,sizeof(tmp));
primes((int)sqrt(r));
memset(nt_prime,0,sizeof(nt_prime));
for(int i=1;i<=m;i++)
{
for(ll j=l/prime[i];j*prime[i]<=r;j++)
{
if(j>1&&j*prime[i]>=l)//防止下标为负
nt_prime[j*prime[i]-l]=1;//注意,倍数必须是大于等于二倍来筛素数
}
}
int cnt=0;
for(ll i=l;i<=r;i++)
{
if(!nt_prime[i-l]&&l!=1)//一定要注意1既不是素数也不是合数,筛的时候从2开始没有把它筛掉
{
tmp[++cnt]=i-l;
}
}
if(cnt<=1)printf("There are no adjacent primes.\n");
else
{
ll Mdis=0,mdis=r-l+1,head,next,sh,sn,mh,mn;
for(int i=1;i<cnt;i++)
{
head=tmp[i+1];
next=tmp[i];
if(Mdis<head-next)
{
Mdis=head-next;
mh=head,mn=next;
}
if(mdis>head-next)
{
mdis=head-next;
sh=head,sn=next;
}
}
printf("%lld,%lld are closest, %lld,%lld are most distant.\n",sn+l,sh+l,mn+l,mh+l);
}
}
return 0;
}
/*2147000000 2147483647
1 2
2146483648 2147483647
2147483047 2147483647
*/
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator