ACM_线性筛 · Mr.li's Blog

什么是线性筛?

筛素数是为了求得一个区间内的所有素数，而把不是素数的筛去。

最普通的办法——判断一个数是不是素数

#define SIZE 1000000

int main(){
    int check[SIZE];
    int prime[SIZE] = {0};
    int pos;
    int flag;
    for (int i = 2 ; i < SIZE ; i++){
        flag = 1;
        for (int j = 2 ; j < sqrt(i) ; j++){
            if (i % j == 0)
                flag = 0;
        }
        if (flag == 1) prime[pos++] = i;
    }
    printf("%.2f", (double)clock()/CLOCKS_PER_SEC);
    return 0;
}

普通筛素数——将不是素数的筛掉

#include <bits/stdc++.h>
using namespace std;

#define SIZE 1000
int main(){
    int checked[SIZE] = {0}; // 如果是1的话就是合数
    int prime[SIZE] = {0};
    int pos = 0;
    int i,j;
    for( i = 2;i < SIZE ; i++){
        if ( ! checked[i] ){
           prime[pos++] = i;
        }
        for( j = 2*i; j < SIZE ; j += i ) checked[j] = 1;
    }
    for( i = 0;i< SIZE ; i++)
        if (prime[i] == 0){
            cout << i-1 << endl;
            // 素数的个数
            break;
        }
    return 0;
}
// output : 168

普通筛素数

基本思想
一次循环筛掉当前素数的倍数
缺点
- 存在重复筛选，比如6既可以被2筛掉，又可以被3筛掉。
- 原因：任意一个整数可以写成一些素数的乘积 $n=p_{1}^{a} * p_{2}^{b} * p_{3}^{c}$ ，其中 $p1<p2<p3$ ，这样这个数n就能被p1,p2和p3筛掉
解决方法：按照一个数的最小素因子筛去(也就是这里的p1)就可以啦，这也就有了线性筛素数

线性筛素数

#define SIZE 1000
int main(){
    int check[SIZE] = {0};//元素值为0代表是素数
    int prime[SIZE] = {0};
    int pos=0;
    for (int i = 2 ; i < SIZE ; i++){
        if (!check[i])//如果是素数
            prime[pos++] = i;

        // ★.区别在于此
        for (int j = 0 ; j < pos && i*prime[j] < SIZE ; j++){
/* cl觉得可以写成for (int j = 0 ;  i*prime[j] < SIZE ; j++)j < pos 是多余的,
如果i是个素数,比如7,那么prime[x]=7,当j=x的时候必然有if (i % prime[j] == 0), 此时x=pos - 1
如果是个合数,比如15,那么肯定有最小素因子使得(i % prime[j] == 0),此时j < pos 
如果i是个偶数,比如8,那么if (i % prime[j] == 0)  此时在2的时候就退出了。j=0 < pos

2019-4-26 j<pos不能删,这个是主要控制j取值的大小的因素,控制取出的都是已知的素数
*/
            
            check[i*prime[j]] = 1;//筛掉
            //标注一
            
            // 通过这步可以找到最小素数因子,
            // 比如12,那么 prime[j] 最先== prime[0] == 2 , 即找到了最小的因子2,
            // 那12就不是个素数,就不用再判断它是不是能被3合成 
            if (i % prime[j] == 0)
                break;
        }
    }
    printf("%.2f", (double)clock()/CLOCKS_PER_SEC);
    return 0;
}

基本思想
当前数字是 $n=p_{1}^{a} * p_{2}^{b} * p_{3}^{c}$ (p1<p2<p3且均为素数)，一次循环筛除小于等于p1的素数乘以n得到的数。比如p1之前有pi,pj和pk三个素数，则此次循环筛掉pi*n,pj*n,pk*n和p1*n ，实现见代码的标注一，prime 里的素数都是升序排列的，break时的prime[j] 就是这里的p1。

优点：没有重复筛同一个数

原因：按照一个数的最小素因子筛选，比如6只按2筛去

从图上我们看到，第一列筛掉的是最小素因子是2的数，第二列筛掉的是最小素因子为3的数，第三列最小素因子是prime[2]==5 ，依次类推，可以把所有的合数都筛掉。

由于每列筛掉的合数都是它自身的平方，即一个素数最小的因子除了1就是它本身，所以 素数的平方的最小素因子就是 它本身 ，而通过i % prime[j] == 0就可以控制不多筛。

因为是按照最小素因子筛选，所以可以保证每个数都只会被筛一遍 ==> 18--9x2

摘自：这只菜鸟总算搞懂了线性筛素数

素数的判别挺有意思的，剪枝的方法可以见我的另一篇博客 : 素数判别