本文共 1646 字，大约阅读时间需要 5 分钟。
// 数论题，增强的筛法，回想素数筛法// 只要筛到最大数的开方，剩下的就是素数// 于是这里，开一个 sqrt(2^31) 大约 65536 的素数表，然后// 对于每个 L~U 的区间，筛掉 sqrt(U) 之内的素数的倍数即可 #include #include #include #include #include #include #include #include #include using namespace std;#define MOD 1000000007#define maxm 10010#define maxn 50010int prim[maxn/3],p;bool f[maxn];int gcd(int a,int b){ int r; while(r=a%b){a=b;b=r;} return b;}bool isp(int n){ if(n==2) return true; if(n%2==0||n==1) return false; int m=(int)(sqrt(n+1.0)); for(int i=3;i<=m;i+=2) if(n%i==0) return false; return true;}void getprime(){ int i,j; f[1]=true; for(i=4;i<=maxn;i+=2) f[i]=true; int m=(int)(sqrt(maxn+1.0)); for(i=3;i<=m;i+=2){ for(j=i*i;j<=maxn;j+=i) f[j]=true; } for(i=1;i<=maxn;i++) if(!f[i]) prim[p++]=i;}int sum[maxn];void sum_divisor(int n){ int i,j; for(i=2;i<=n/2;i++) for(j=i+i;j<=n;j+=i) sum[j]+=i; sum[1]=-1;}int v[maxn*20];int L,U,len;void shaixuan(){ int i=0; long long j; long long l=L,r=U; while(prim[i]<47000){ j=(l-1+prim[i])/prim[i]; // printf("%lld ",j); if(j==1) j++; for(j=prim[i]*j;j<=r;j+=prim[i]) v[j-l]=1;//,printf("%lld ",j); i++; }}int main(){ int n; int m; int i,k; int l,r; // int tp=~(1<<31); // m=sqrt(tp+1.0); // printf("%d",m); getprime(); int maxl,maxr,maxlen,minl,minr,minlen; while(scanf("%d %d",&L,&U)!=EOF){ len=U-L; for(i=0;i<=len;i++) v[i]=0; shaixuan(); l=-1; maxlen=0; minlen=MOD; if(L==1) v[0]=1; for(i=0;i<=len;i++) if(!v[i]){ // printf("%d ",i+L); if(l==-1)l=i; else{ if(i-l>maxlen){ maxlen=i-l; maxl=l+L; maxr=i+L; } if(i-l
转载于:https://www.cnblogs.com/372465774y/p/3209263.html