质数的筛法

绝地灬酷狼 2022-11-15 15:49 199阅读 0赞

**上一篇博客：[LeetCode 1006. 笨阶乘——每日一题][LeetCode 1006.]**

>  写在前面：大家好！我是`AC-fun`,我的昵称来自两个单词`Accepted`和`fun`。我是一个热爱ACM的蒟蒻。如果博客中有不足或者的错误的地方欢迎在评论区或者私信我指正，感谢大家的不吝赐教。我的唯一博客更新地址是：[https://ac-fun.blog.csdn.net/][https_ac-fun.blog.csdn.net]。非常感谢大家的支持。一起加油，冲鸭！  
>  `用知识改变命运，用知识成就未来！加油 (ง •̀o•́)ง (ง •̀o•́)ง`

# 定义 #

若一个正整数无法被除了 **1** 和它自身之外的任何自然数整除，则称该数为`质数`（或者素数），否则称该自然数为`合数`。

# 质数的判定 #

## 试除法 ##

“试除法”是最简单也是最经典的确定性算法，可以从 **2 ~ n** 依次试除，判断 **n** 是否有 `约数`，如果有证明 **n** 不是质数，否则证明 **n** 是质数。在竞赛中如果直接循环判断到 **n** ，时间复杂度为 **O(n)** 一般都会 `TLE`。

这里可以再进行一下优化,假设 **d** 可以整除 **n**，那么它们的商 **n / d** 也能整除 **n**。假设在 **d** 与 **n / d** 中 **d** 是较小的那个数，那么 **n / d >= d** 所以 **d <=  n \\sqrt\{n\} n**。所以每次判断只需要判断到  n \\sqrt\{n\} n 即可。这样时间复杂度就变为了 **O( n \\sqrt\{n\} n)**。

bool is_prime(int x) { 
        if (x < 2) return false;
        for (int i = 2; i <= x / i; i++) { 
            if (x % i == 0) return false;
        }
        return true;
    }

## 朴素筛法 ##

根据质数的定义可以得到任何整数 **x** 的倍数都不是质数。所以我们可以从 **2** 开始，从小到大扫描每一个数 **x** 的倍数，那么其倍数就一定是合数而不是质数。当扫描到一个数时，如果其未被标记，则它不能被 **2 ~ x - 1** 之间的任何数整数，说明该数就是质数。该算法的时间复杂度是 **O(n log ⁡ n \\log\{n\} logn)**。

#include<iostream>
    
    using namespace std;
    
    const int N = 1e6 + 10;
    
    int prime[N], cnt;
    bool st[N];
    
    void get_peime(int n) { 
        for (int i = 2; i <= n; i++) { 
            if (!st[i]) prime[cnt++] = i;
            // 将 i 的倍数筛掉
            for (int j = i + i; j <= n; j += i) st[j] = true;
        }
    }
    
    int main() { 
        int n;
        cin >> n;
        
        get_peime(n);
        
        cout << cnt << endl;
        return 0;
    }

## 埃氏筛法 ##

这里需要首先明确什么是 [算数基本定理][Link 1] 也叫 `唯一分解定理` 。算术基本定理可表述为：任何一个大于1的自然数 N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积。所以我们就可以得到每个合数必定是某个比它小的质数的倍数，所以我们只需要从小到大将所有质数的倍数筛掉，剩下的必然全都是质数。

这样就不用将所有的数都筛一遍，只有当当前的数是质数的时候才开始筛。优化后的时间复杂度为 **O(n log ⁡ log ⁡ n \\log\{\\log\{n\}\} loglogn)**。该算法的效率大约是朴素筛法的 **3** 倍。该算法实现简单，在数据范围为 **n <= 106** 时效率已经非常接近与线性。

#include<iostream>
    
    using namespace std;
    
    const int N = 1e6 + 10;
    
    int prime[N], cnt;
    bool st[N];
    
    void get_peime(int n) { 
        for (int i = 2; i <= n; i++) { 
            if (!st[i]) { 
                prime[cnt++] = i;
                // 当 i 是质数的时候将 i 的倍数筛掉
                for (int j = i + i; j <= n; j += i) st[j] = true;
            }
        }
    }
    
    int main() { 
        int n;
        cin >> n;
        
        get_peime(n);
        
        cout << cnt << endl;
        return 0;
    }

## 线性筛法 ##

虽然`埃式筛法`在筛法中做了优化，但是埃式筛法任然会重复筛掉合数。例如 **12** 即会被 **2** 筛掉又会被 **3** 筛掉。而线性筛法则可以避免这个问题，线性筛法（也称为欧拉筛法）的核心思想是：保证每个合数只被其最小的质因子筛掉。这样就可以保证每个合数只会被它最小的质因子筛掉一次，时间复杂度为 **O(N)**。

线性筛法的具体操作步骤为：

1.  一次遍历 **2 ~ n** 之间的每一个数 **i**，如果 **i** 未被标记那么说明当前的 **i** 为质数，那么就将其保存下来。
2.  然后从小到大遍历每一个质数 **p**，将每一个 **p \* i** 标记为合数，直到 **i % p == 0** 为止。因为我们是从小到大遍历的每一个质数，只要 **i % p == 0** 就说明 **p** 一定是 **i** 的最小质因子，那么此时 **p** 就一定是 **p \* i** 的最小质因子。如果再往后计算，那么就无法保证每个合数只会被它最小的质因子只筛掉一次了。当 **i % p != 0** 时，由于我们是从小到大进行遍历的，而且 **p** 不是 **i** 的质因子，所以在 **i % p == 0** 之前都可以保证 **p** 是 **p \* i** 的最小质因子。

根据 [算数基本定理][Link 1] 任何一个合数一定会被筛掉，因为任何一个合数一定会存在一个最小质因子。

当数据规模在 **n == 106** 时，线性筛法和埃式筛法所需要的时间差不多，但是当数据规模在 **n == 107** 时线性筛法所需要的时间大约是埃式筛法的一半。线性筛法是竞赛中比较常用的算法。

#include<iostream>
    
    using namespace std;
    
    const int N = 1e6 + 10;
    
    int prime[N], cnt;
    bool st[N];
    
    void get_peime(int n) { 
        for (int i = 2; i <= n; i++) { 
            if (!st[i]) prime[cnt++] = i;
            for (int j = 0; prime[j] <= n / i; j++) { 
                st[prime[j] * i] = true;
                if (i % prime[j] == 0) break;
            }
        }
    }
    
    int main() { 
        int n;
        cin >> n;
        
        get_peime(n);
        
        cout << cnt << endl;
        return 0;
    }

--------------------

> 未完待续，持续更新中……  
> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTc1NTA3_size_16_color_FFFFFF_t_70][]

[LeetCode 1006.]: https://ac-fun.blog.csdn.net/article/details/115368340
[https_ac-fun.blog.csdn.net]: https://ac-fun.blog.csdn.net/
[Link 1]: https://baike.baidu.com/item/%E7%AE%97%E6%9C%AF%E5%9F%BA%E6%9C%AC%E5%AE%9A%E7%90%86/10920095?fr=aladdin
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTc1NTA3_size_16_color_FFFFFF_t_70]: /images/20221022/d4f64ed91eca474cb088fb99e56395c8.png