质数筛法

埃氏筛

2 3 4 5 6 7 8 9

2 3 ~~4~~ 5 ~~6~~ 7 ~~8~~ 9 //筛掉2的倍数

2 3 5 7 ~~9~~ //筛掉3的倍数

复制

例：

#include <cstdio>
#include <cmath>

bool b[100000005];

int main() {
    int n;
    scanf("%d",&n);
    for (int i=2; i <= sqrt(n); i++) { // 注意枚举质数的范围
        if (!b[i]){ // b[i]值为0表示i为质数
            for (int j = i; j <= n/i; j++) { // 筛掉i的倍数
                b[i*j]=1;
            }
        }
    }

    for (int i = 2; i <= n; i ++) {
        if (!b[i]){
            printf("%d ",i);
        }
    }
    return 0;
}

复制

11 行处为一个小优化： $𝑖$ 的倍数从 $𝑖 2$ 开始枚举（考虑 $𝑗 = 𝑘 \cdot 𝑖 < 𝑖 \cdot 𝑖$ ， $𝑗$ 一定会被 $𝑘$ 的质因数筛去）

举个例子：筛 $2$ 的倍数时，被打标记的数字分别是

1	22,23,24......2n/2 复制

那么我们筛

𝑖

的倍数时，无优化算法被打标记的数分别是

1	i2,i3,i4.......in/i 复制

可以发现，

2 𝑖

和

4 𝑖

(即

2 \cdot 2 𝑖

)在枚举

2

的倍数时已经被打过标记了
其他任意一个

𝑘 \cdot 𝑖, 2 ⩽ 𝑘 < 𝑖

都同理。

线性筛 (转载)

版权声明：下方为lyf_018原创文章，遵循 CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/qq_41653433/article/details/88976544

初始时，假设全部都是素数，当找到一个素数时，显然这个素数乘上另外一个数之后都是合数。如果按照埃氏筛做法枚举每个质数的倍数，会造成重复筛除，影响效率。

例如 $30 = 5 \times 3 \times 2$ ，它被 $2 \times 15$ 筛了一次，又被 $3 \times 10$ 筛了一次，为了解决这个问题，线性筛应运而生：

int mark[MAXN];  
int prime[MAXN];  
  
//判断是否是一个素数  Mark 标记数组 index 素数个数  
int Prime(int n){  
    int index = 0;  
    for(int i = 2; i < n; i++){  
        //如果未标记则得到一个素数  
        if(mark[i] == 0) prime[++index] = i;  
        //标记目前得到的素数的i倍为非素数  
        for(int j = 1; j <= index && prime[j] * i < n; j++){  
            mark[i * prime[j]] = 1;  
            if(i % prime[j] == 0) break;  
        }  
    }  
    return index;  
}

复制

利用了每个合数必有一个最小素因子。每个合数仅被它的最小素因子筛去正好一次。所以为线性时间。
代码中体现在：

1	if(i%prime[j]==0) break; 复制

𝑝 𝑟 𝑖 𝑚 𝑒

数组中的素数是递增的,当

𝑖

能整除

𝑝 𝑟 𝑖 𝑚 𝑒 𝑗

，那么

𝑖 \cdot 𝑝 𝑟 𝑖 𝑚 𝑒 𝑗 + 1

这个合数肯定也可以被

𝑝 𝑟 𝑖 𝑚 𝑒 𝑗

筛掉，因为

𝑖

中含有

𝑝 𝑟 𝑖 𝑚 𝑒 𝑗

𝑝 𝑟 𝑖 𝑚 𝑒 𝑗

比

𝑝 𝑟 𝑖 𝑚 𝑒 𝑗 + 1

小。

接下去的素数同理，所以不用筛下去了。
在满足 $𝑖 m o d 𝑝 𝑟 𝑖 𝑚 𝑒 𝑗 = 0$ 这个条件之前以及第一次满足该条件时, $𝑝 𝑟 𝑖 𝑚 𝑒 𝑗$ 必定是 $𝑝 𝑟 𝑖 𝑚 𝑒 𝑗 \cdot 𝑖$ 的最小因子

本文采用 GNU 自由文档许可证许可协议，转载请注明出处。