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