质数筛法

埃氏筛

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 行处为一个小优化：\(i\) 的倍数从 \(i^2\) 开始枚举（考虑 \(j = k\cdot i<i\cdot i\)， \(j\) 一定会被 \(k\) 的质因数筛去）

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

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

那么我们筛 \(i\) 的倍数时，无优化算法被打标记的数分别是

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

可以发现，\(2i\) 和 \(4i\) (即 \(2\cdot 2i\))在枚举 \(2\) 的倍数时已经被打过标记了
其他任意一个 \(k\cdot i, 2\leqslant k< i\) 都同理。

线性筛 (转载)

版权声明：下方为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;

\(prime\) 数组中的素数是递增的,当 \(i\) 能整除 \(prime_j\)，那么 \(i\cdot prime_{j+1}\) 这个合数肯定也可以被 \(prime_j\) 筛掉，因为 \(i\) 中含有 \(prime_j\), \(prime_j\) 比 \(prime_{j+1}\) 小。

接下去的素数同理，所以不用筛下去了。
在满足 \(i\ \bmod \ prime_j = 0\) 这个条件之前以及第一次满足该条件时,\(prime_j\) 必定是 \(prime_j\cdot i\) 的最小因子

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