UVA10140 Prime Distance (素数的判定） HQG

素数的判定） HQG"/>

UVA10140 Prime Distance (素数的判定） HQG

题意：
求l到r的素数中距离最小的是多少，最大的是多少，没有就输出
There are no adjacent primes.

思路：
发现l和r很大，但是r-l的值不大。于是考虑缩短存储：
prime[i]表示i+l是不是质数。
于是就只用打一波素数筛就可以了（可以不用线性筛也能过），之后模拟。

注意：l,r都要long long 不然 像2147483647这样的数据就RE了。

AC代码：

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std ;
const int inf = 0x3f3f3f3f ;
bool prime[1000010] ;//prime[i] 意味着i+l是不是质数 
int p[1000010];
int maxlen,minlen,max1,max2,min1,min2 ;
long long l,u ;
int tot ;
long long sqz(long long a,long long b){ //a/b上取整 if (a%b!=0) return (a/b+1)*b ;else return a ; 
}
long long max(long long a,long long b){if (a>b) return a ;else return b ; 
}
void init(){int up=(int)sqrt(1.0*u)+1;for (long long i=2;i<=up;i++){int total=0 ;for (long long j=max(i*i,sqz(l,i));j<=u;j+=i) total++,prime[(int)j-l]=false ;}for (int i=0;i<=u-l;i++) if (prime[i]) p[++tot]=i+l ;for (int i=2;i<=tot;i++){if (p[i]-p[i-1]>maxlen){maxlen=p[i]-p[i-1] ;max1=p[i] ;max2=p[i-1] ;}if (p[i]-p[i-1]<minlen){minlen=p[i]-p[i-1] ;min1=p[i] ;min2=p[i-1] ;}}
}
int main(){while(~scanf("%lld%lld",&l,&u)){memset(prime,true,sizeof(prime)) ;tot=0 ;if (l==1) prime[0]=0 ; maxlen=0,minlen=inf,max1=0,max2=0,min1=0,min2=0 ;init() ;if (tot<2) printf("There are no adjacent primes.\n") ;else printf("%d,%d are closest, %d,%d are most distant.\n",min2,min1,max2,max1) ;}return 0 ; 
}