模板 - 数学 - 数论 - 简单数论 - 区间素数筛-白红宇

模板 - 数学 - 数论 - 简单数论 - 区间素数筛

阅读量：4646 次

发布时间：2019-06-09

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

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;  const int MAXN = 1e6+1e3;   //待筛的区间[L,R]长度const int N = 50001;//保证大于(2^31-1)的算数平方根bool prime[MAXN];bool seive[N];typedef long long ll;int L,R,len; void seg_seive(ll L,ll R)   //区间筛法{    len=R-L+1;    for(int i=0;i
         
          =0) prime[1-L]=0;   //易错因为1不是素数也不是合数，这也是区间筛的一个易错bug    for(ll i=2; i*i<=R ;i++)    {        if(seive[i])        {            for(ll j=max((ll)2,(L-1+i)/i)*i;j<=R;j+=i)  //第二个易错点，j必须从大于1，因为L可能小于i，但是seive[i]是素数。                prime[j-L]=false;        }    }}int main(){     for(int i=2;i
          
           =0) { if(mmax
           
            i-t) mmin=i-t,lmin=t+L,rmin=i+L; t=i; } else t=i; } if(mmax>0) printf("%d,%d are closest, %d,%d are most distant.\n",lmin,rmin,lmax,rmax); else puts("There are no adjacent primes."); } return 0;}