UVA10140 Prime Distance-白红宇

UVA10140 Prime Distance

阅读量：7125 次

发布时间：2019-06-28

本文共 1237 字，大约阅读时间需要 4 分钟。

给定两个整数 $L,R(1<=L<=R<=2^{31},R-L<=10^6)L,R(1<=L<=R<=231,R−L<=106)，求闭区间 [L,R][L,R] 中相邻两个质数的差的最小值和最大值是多少，分别输出这两个质数。$

首先我们发现： $L\sim RL∼R 之间的质数。$

显然有推论：任意一个合数 $\sqrt xx 的质因子。$

所以我们可以筛出 $[1,\sqrt R][1,R] 之间的所有质数，对于每个质数 pp，把 [L,R][L,R] 中能被 pp 整除的数标记为合数。最终没有被标记的数就是质数，对相邻的质数两两比较，找出差值最小和最大的即可。$

#include #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;typedef long long LL;#define res register int const LL N=1e6+100;LL v[N],p[N],tot;LL L,R;inline LL max(LL a,LL b){return a>b?a:b;}inline LL min(LL a,LL b){return a
          
           n/i || p[j]>v[i]) break; v[i*p[j]]=p[j]; } }}LL a[N],cnt;LL vis[N];int main(){ primes(N); while(cin>>L>>R) { memset(vis,0,sizeof(vis)); for(res i=1 ; i<=tot ; i++) { for(res j=L/p[i] ; p[i]*j<=R ; j++) { LL x=j*p[i]; if(j>1 && x>=L) vis[x-L]=1; } } if(L==1) vis[0]=1; cnt=0; for(res i=L ; i<=R ; i++) if(!vis[i-L]) a[++cnt]=i; if(cnt<=1) { puts("There are no adjacent primes."); continue; } LL maxn(-1e9),minn(1e9),x,y; for(res i=1 ; i
           
            maxn) maxn=a[i+1]-a[i],x=a[i],y=a[i+1]; printf("%lld,%lld are most distant.\n",x,y); } return 0;}