【模板】筛质数

需要注意的是该筛法对后序积性函数应用十分有用

朴素法

在大于1的[自然数] 中，除了1和它本身以外不再有其他[因数] 的自然数

法1.暴力试除法

1
2
3
4
5
6
7


bool is_primie(int n){
    if(n<=1) return false;
    for(int i = 2;i<n;i++){
        if(n % i == 0 ) return false;
    }
    return true;
}

法2 一个因数出现必然存在另一个因数 所有的约数是成对出现的既你n 能整除一个因子所得到的数那你必然能整除刚整除得到的数

记为 d | n , $\frac{n}{d} | n $ ，n能被d 整除那么 n也能被 $\frac{n}{d}$整除

也就是说我们只需要枚举较小的那个因数就必然能找到较大的那个因数。

所以要d <= n/d => d*d <=n ,但有可能爆int 所以改为除法好点

d <= sqrt(n)

1
2
3
4
5
6
7


bool is_primie(int n){
    if(n<=1) return false;
    for(int i = 2;i<=n/i;i++){ // i*i*1LL <= n also  
        if(n % i == 0 ) return false;
    }
    return true;
}

埃氏筛质数

luoguP3383

质数x质数一定等于合数，因为该除了可以被1和自身整除还可以被两个相同的质数整除要不然你怎么相乘得到该数…

也就是说得到的合数一定是该质数的倍数既，质数的倍数一定是合数。

所以筛选质数的时候就可以把质数的倍数给剔除。剩下的就是质数

但是该方法的缺点是会重复剔除。复杂度 o(N*loglogn) 近乎o(N).

复杂度 n/2 + n/3 +….+n/n = n * (1/2+1/3+…+1/n) 调和级数 = ln n + c(欧拉常数)

o(nln n) 优化：

但是上面是把每一个数的倍数都删掉，其实不用根据整数惟一分解定理只需要把质数的倍数删掉即可(合数的就不用管了),。直接把下面的倍数扔去if里面

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


typedef long long LL;
const int N = 100000010;
LL prim[N];
bool vis[N];
LL cnt = 0;
void p(int n){
    for(int i = 2;i<=n;++i){
        if(!vis[i]){
            prim[++cnt] = i;
            //开始划倍数(必然为合数)
            //注意i*i 爆int
            for(LL j = i*i;j<=n;j+=i){//j = 2*i ?
                vis[j] = true;
            }
        }
    }
}

關於爲什麽要i*i 而不是i*2 当然也可以但是i*i 可跳过如6 在2已被划 3就没必要划

证明:

从[i,i*i)这段区间可以被[2,i-1]划为什么?

根据整数唯一分解定理

$$ n=p_1^{\alpha_1} p_2{ }^{\alpha_2} \cdots p_s^{\alpha_s}, (p_1<p_2<p_3<…<p_n) $$ 反证， i*i 分解后质数范围在[2,i-1] 里所以可以交给之前的质数划，自己本身从i*i出发即可

线性筛法(欧拉筛法)

P3912 素数个数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

朴素筛法使用质数筛选出来的合数 会有重复 而重复的根本原因是乘出来的合数可以被多个因数获得，而在相乘(加)的过程中所得到的合数因子有可能包含之前用来相乘的质数。也就意味着该合数是之前质数的倍数意味着之前的质数累加和当前质数的累加会有重复部分如 6 这个合数在埃氏筛里被2，3筛了两次

既要确保每一个合数只会被最小质因数筛掉即可保证每个合数只会被筛选一次，先理解算法流程待会再证明

注意到筛法求素数的同时也得到了每个数的最小质因子。

算法流程：

如果当前数没划掉必定是质数记录该质数(因为你一开始是从2开始后面又经过筛选)
从小到大枚举当前已记录的质数，如果筛选的合数超过筛选的范围则中断
1. 条件 i % p[j] == 0 , p[j]也一定是 i的最小质因子(因为是从小到大枚举当前的质数)
  - 如果i是质数那么枚举到的 p[j]就是自身中断
  - 如果i是合数那么最多枚举到自身的==最小质因数== 直接中断防止重复标记.
所以筛选的每一个数都是最小质因子得到，而根据惟一性定理，一个合数一定存在一个最小质因子, 也就意味着一个合数只被筛选了一次既为线性.

在线性筛中每个合数m都是被 最小质因子筛选掉的其中 m = i * p[j] 而 p[j] 又是从小到大枚举，正因为是从小到大枚举质因子p[j] 所以可以拿到最小质因子那么怎么拿到最小质因子就是通过

i % p[j] == 0 这个条件

若i能被pj 整除那么pj一定是 i的最小质因子因为在第二层循环中是从小到大枚举所有质数，一旦发现取余为0 那么 pj就是 i的最小约数，又因为该约数还是质数所以就是i的最小质因数，

同理也一定是m的最小质因数因为是从小到达枚举的质数，由于m = i*pj得来若不是m的最小质因数那么在前面的i 就已经被筛选掉

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


typedef long long LL;
const int N = 100000010;
LL prim[N]; //记录质数
bool vis[N]; //划掉的合数
LL cnt = 0;
void p(LL n){//[2,n]多少个质数
    for(LL i = 2;i<=n;++i){
        if(!vis[i]) prim[++cnt] = i;
        //从小到大枚举质数
        for(LL j = 1;1ll*i*prim[j]<=n;++j){
            vis[i*prim[j]] = 1;
            if(i % prim[j] == 0) break;//确保只能被最小质因子划掉
        }
    }
}

Q 会漏解吗？

假设存在一个合数m没有被标记，那么m必然有一个最小质因数p。但是在遍历到p时，我们会标记p的所有倍数，包括m，所以矛盾。因此，任何合数都会被标记。

Q 为什么保证了最小质因子就能保证唯一性？

每个合数都会被它最小的质因数标记，因此在整个筛法过程中，每个质数只会被标记一次。如果一个数有多个质因数，那么它会在被最小的质因数标记后，就不再被其他质因数标记，因为其他质因数的倍数会在更早的时候被标记。

如果一个合数被多个质数筛选，那么它的最小质因子一定是其中一个质数，而其他合数都会在它的最小质因子筛选时被排除掉，因此不会重复筛选。因此，只要保证每个合数只能被它的最小质因子筛选，就能保证每个合数只被筛选一次。

Q 会不会有质数被当成合数筛(划)掉？

不可能，因为 m 是通过 i*pj得来，约数显然不只一个而第一层循环又从2开始，怎么相乘都不可能得到质数

代码参考

https://www.cnblogs.com/dx123/