质数的筛法定义质数的判定

60 阅读 0 评论 40 点赞

我是靠谱客的博主强健朋友，最近开发中收集的这篇文章主要介绍质数的筛法定义质数的判定，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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

写在前面：大家好！我是晴空๓。如果博客中有不足或者的错误的地方欢迎在评论区或者私信我指正，感谢大家的不吝赐教。我的唯一博客更新地址是：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$ 。所以每次判断只需要判断到 $n$ 即可。这样时间复杂度就变为了 O( $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}$ )。

#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;
}

埃氏筛法

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

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

#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)。

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

一次遍历 2 ~ n 之间的每一个数 i，如果 i 未被标记那么说明当前的 i 为质数，那么就将其保存下来。
然后从小到大遍历每一个质数 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 的最小质因子。

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

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

#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;
}