题目：Prime Distance

传送门：

分析：

1. $ [L,R] $ 只有1e6，于是暴力写了个millRabin测试，时间复杂度大约$ O(N*k*logN) $然后Tle。

2. 可以考虑一下二次筛法。$ [L,R] $ 中每一个合数一定包含一个不超过$ \sqrt n $ 的质因子。

3. 我们把$ [ 1,\sqrt R ] $ 的质数筛出来。

4. 再标记 $ i*p, i \in [ [\frac{L}{p}] , [\frac{R}{p}] ] $ ,就是把$ [L,R] $之间的合数筛掉。这个常数很小，时间复杂度$ O(\sum{\frac{R-L}{p}}) $ 。 

5. 剩下的就是质数啦。

 

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;typedef long long LL;const int INF=1<<30,maxN=50005;int pn,p[maxN],vis[1000007];void getPrime(){    for(int i=2;i
         
          0 && j<=(LL)R;j+=p[i])use[j]=1;    }    if(L==1)vis[0]=1;}int main(){    getPrime();    for(int L,R;~scanf("%d%d",&L,&R);){        int i=L,last=0,*use=vis-L;int mn0=0,mn1=INF,mx0=0,mx1=0;        getPrimeInLR(L,R);        for(;i<=R && !last;++i)if(!use[i])last=i;        for(;i>0 && i<=R;++i)            if(!use[i]){                if(i-last
          
           mx1-mx0){mx1=i;mx0=last;} last=i; } if(!mn0)puts("There are no adjacent primes."); else printf("%d,%d are closest, %d,%d are most distant.\n",mn0,mn1,mx0,mx1); } return 0;}
          
         
        
       
      
     

 

素数筛的常数计算：

#include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;typedef long long LL;const int INF=1<<30,maxN=50005;int pn,p[maxN],vis[1000007];void getPrime(){    for(int i=2;i