ACM.素数筛

清疚 2023-07-05 11:57 3阅读 0赞

## 一.埃氏筛 ##

筛法的思想是去除要求范围内所有的合数，剩下的就是素数 了，而任何合数都可以表示为素数的乘积，因此如果已知一 个数为素数，则它的倍数都为合数。合数的倍数一定会在筛素数倍数时候被筛掉，所以只筛素数就好，只把质数的 数筛掉 ，就是找到一个质数，把它的倍数全部标记为合数。

**时间复杂度为nloglogn，接近线性，一般来说足够**

## 二.线性筛 ##

素数筛可以优化，普通的线性筛法虽然大大缩短了求素数的时间， 但是实际上还是做了许多重复运算，比如2\*3=6，在素数2的时候筛选了一遍， 在素数为3时又筛选了一遍。如果只筛选小于等于素数i的素数与i的乘积， 既不会造成重复筛选，又不会遗漏。时间复杂度几乎是线性的，是一个逐渐后移的动态判断的过程。

const int N=1e7+1;
    int prime[N];
    int b[N];
    int cnt=0,max1=1e7;
    int init()
    {
        
        memset(b,1,sizeof(b));//默认初始都是质数
        b[0]=b[1]=0;//特殊判断0和1不是质数
        for(int i=2;i<=max1;i++)
        {
        
            if(b[i])
            {
        
                prime(++cnt)=i;//是质数，打到素数表中
            }
            for(int j=1;j<=cnt&&prime[j]*i<=max1;j++)
            {
        
                b[prime[j]*i]=0;
                if(i%prime[j]==0) break;//防止重复操作，如果能除尽就停止1，后面会有其他的数把他判断掉。
            }//例如i=4时，4*2=8，4整除2，将8判断就可以停止了，不用判断下一个4*3了，12可以由后面的6*2判断。
        }
        return 0;
    }

**时间复杂度接近线性**  
我们要筛1到n中的素数，然后先默认他们都是素数，最外层枚举 1~n的所有数，  
如果它是素数，就加到素数表，  
对于每一个枚举的i ,枚举素数表里的数，然后素数就会标记自己 i 倍的数不是素数，（素数的倍数不是素数）  
枚举素数表什么时候停？枚举到i的最小质因子，标记完就可以停 了，保证每个数只被他的最小质因子筛掉。  
**例如**  
：外层i=15时，素数表里：2,3,5,7,11,13 2*15=30，把30筛掉；3*15=45，把45筛掉，因为15%3==0，退 出里面的循环；  
15是被3筛掉的，因为3是15的最小素因子。

通过素数筛得到了一个按顺序排好的数组后，就可以判断是否是素数了。

## 判断素数 ##

只需要枚举I到根号x即可。

int judge(long long n){
        
    int flag=0;
    for(int i=1;prime[i]<=sqrt(n*1.0);i++)
    if(n%prime[i]==0) {
        flag=1;break;}
    if(n==1) flag=1;
    return flag;
    }

通过将素数筛函数与判断函数结合，可以处理函数的判断问题。

因为素数筛的过程中，值只有0和1，那么我们可以直接进行优化，创建一个布尔类型的数组，省空间，判断函数也不用了，直接看该数对应的位置上是0还是1就行了。

const int N=1e7+10;
    int prime[2000000];
    bool b[N],c[N];
    int cnt=0,max1=N;
    int init(){
        
        memset(b,1,sizeof(b));
        b[0]=b[1]=0;
        for(int i=2;i<=max1;i++)
        {
        
            if (b[i])
            {
        prime[++cnt]=i;
            }
             for(int j=1;j<=cnt&&prime[j]*i<=max1;j++)
                {
        
                    b[prime[j]*i]=0;
                    if (i%prime[j]==0) break;
                }
        }
        return 0;
    }//查询x是否为素数，只需看b【x】的值是否为真即可。

2020.2.14，上午只做出来三道题（8/3），数论菜，一下午的gta，肝不动了，晚上看会直播写会博客，明年今日又是怎样的。（23.18）