zoj 1842 Prime Distance

// 数论题,增强的筛法,回想素数筛法
// 只要筛到最大数的开方,剩下的就是素数
// 于是这里,开一个 sqrt(2^31) 大约 65536 的素数表,然后
// 对于每个 L~U 的区间,筛掉 sqrt(U) 之内的素数的倍数即可
#include <iostream>
#include <math.h>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <string.h>
using namespace std;
#define MOD 1000000007
#define maxm 10010
#define maxn 50010
int prim[maxn/],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==) return true;
if(n%==||n==) return false;
int m=(int)(sqrt(n+1.0));
for(int i=;i<=m;i+=)
if(n%i==) return false;
return true;
}
void getprime(){
int i,j;
f[]=true;
for(i=;i<=maxn;i+=)
f[i]=true;
int m=(int)(sqrt(maxn+1.0));
for(i=;i<=m;i+=){
for(j=i*i;j<=maxn;j+=i)
f[j]=true;
}
for(i=;i<=maxn;i++)
if(!f[i]) prim[p++]=i;
}
int sum[maxn];
void sum_divisor(int n){
int i,j;
for(i=;i<=n/;i++)
for(j=i+i;j<=n;j+=i)
sum[j]+=i;
sum[]=-;
}
int v[maxn*];
int L,U,len;
void shaixuan(){
int i=;
long long j;
long long l=L,r=U;
while(prim[i]<){
j=(l-+prim[i])/prim[i];
// printf("%lld ",j);
if(j==) j++;
for(j=prim[i]*j;j<=r;j+=prim[i])
v[j-l]=;//,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=;i<=len;i++) v[i]=;
shaixuan();
l=-;
maxlen=;
minlen=MOD;
if(L==) v[]=;
for(i=;i<=len;i++)
if(!v[i]){// printf("%d ",i+L);
if(l==-)l=i;
else{
if(i-l>maxlen){
maxlen=i-l;
maxl=l+L;
maxr=i+L;
}
if(i-l<minlen){
minlen=i-l;
minl=l+L;
minr=i+L;
}
l=i;
}
}
if(maxlen){
printf("%d,%d are closest, %d,%d are most distant.\n",minl,minr,maxl,maxr);
}else printf("There are no adjacent primes.\n");
} return ;
}
上一篇:camunda框架学习(十一)信号系列


下一篇:mysql组合索引顺序参考