质数的基础知识 | JoeyDDong's Blog

本文介绍了质数的判别以及筛法相关的算法知识。

质数的定义：在大于 1 的整数中，如果只能被 1 和本身整除，就被称为质数，或素数。

1. 质数的判定——试除法

方法 1：基本方法

是最笨的方法，复杂度为。因为没有经过优化，不建议使用。

bool is_prime(int n){
    // 如果 n < 2 则肯定不为质数
    if( n < 2 ) return false;
    for(int i = 2 ; i < n ; i++){
        // 任何一个数 i 能整除 n，说明 n 不是质数
        if( n % i == 0) return false;
    }
    return true;
}

方法 2：优化方法

性质：如果能整除，那么也能整除。（即的约数都是成对出现的，例如，2 能整除 12，6 也能整除 12 ）。

所以我们可以只枚举一对中较小的那一个。那么只需要枚举验证 $，$ 之间的数即可。复杂度为。

AcWing 866: 试除法判定质数

问题链接：https://www.acwing.com/problem/content/868/

题目：

给定 n 个正整数，判定每个数是否是质数。

数据范围：

解题思路：

// Problem: https://www.acwing.com/problem/content/868/
// 质数判定
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

int n, x;

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

void solve() {
    cin >> n;
    while (n--) {
        cin >> x;
        if (is_prime(x))
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
}

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    solve();
    return 0;
}

注意：判断条件处最佳写法为： i <= n / i 。

不推荐写成 i <= sqrt(n) 因为每次都会计算一次 sqrt，非常的慢，影响执行速度；

不推荐写成 i * i <= n 因为当非常大，逼近的上限时，容易导致的结果溢出变为一个负数，此时的程序时不稳定的。

2. 分解质因数——试除法

质因数：是指能够整除给定正整数的质数。

1 没有质因子。
5 只有 1 个质因子，5 本身。（5 是质数）
6 的质因子是 2 和 3。(6 = 2 × 3)
2、4、8、16 等只有 1 个质因子：2。（2 是质数，4 =2²，8 = 2³，如此类推）
10 有 2 个质因子：2 和 5。(10 = 2 × 5)

从小到大尝试 n 的所有的因数。只需要枚举到 sqrt(n) 即可（因为 n 中最多只包含一个大于 n 的质因数）

时间复杂度最慢是

AcWing 867: 分解质因数

问题链接：https://www.acwing.com/problem/content/869/

题目：

给定个正整数，将每个数分解质因数，并按照质因数从小到大的顺序输出每个质因数的底数和指数。

数据范围：

解题思路：

#include <iostream>
#include <algorithm>
using namespace std;
void divide(int x){
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
        {
            int s = 0;
            while (x % i == 0) x /= i, s ++ ;
            cout << i << ' ' << s << endl;
        }
    if (x > 1) cout << x << ' ' << 1 << endl;
    cout << endl;
}
int main(){
    int count;
    cin >> count;
    while(count--){
        int n;
        cin >> n;
        divide(n);
    }
    return 0;
}

3. 质数筛选

备注：质数其实没有那么多。100 万以内，大概有 8 万个质数。

方法 1：基本筛法

这种筛选方法的时间复杂度为：

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1000010;
int primes[N] , cnt ;
bool st[N];

void get_primes(int n){
    for(int i = 2 ; i <= n ; i++ ){
        // 如果这个数已经被筛过了，那么留下的数是一个质数，直接就存到 primes 数组中
        if(!st[i]){
            // 把这个质数存进 primes 数组中
            primes[ cnt ++ ] = i ;
        }
        // j 从 2i 开始循环，查看i的倍数，给它赋值为true，标记他不是一个质数
        for(int j = i + i ; j <= n ; j += i) st[j] = true;
    }
}

int main(){
    int n;
    cin >> n ;
    get_primes(n);
    cout << cnt << endl;
    return 0;
}

方法 2：埃氏筛法

质数定理：1 ～ n 中，有个质数。

这个方法中的时间复杂度约为，基本上和复杂度是一个级别的。

这个算法也称为 埃氏筛法。

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1000010;
int primes[N] , cnt ;
bool st[N];

void get_primes(int n){
    for(int i = 2 ; i <= n ; i++ ){
        // 确认了这个数是一个质数了
        if(!st[i]){
            // 把这个质数存进 primes 数组中
            primes[cnt++] = i;
            // 只需要把质数的倍数筛掉，就可以了
            for(int j = i+i ; j <= n ; j += i) st[j] = true;
        }
    }
}

int main(){
    int n;
    cin >> n;
    get_primes(n);
    cout << cnt << endl;
    return 0;
}

方法 3：线性筛法

n 只会被最小质因子筛掉

每一个数只会被最小质因子筛一次，所以是线性的时间复杂度为。

注：下面两个代码的 primes 数组声明方式不一样。一个用普通数组，一个用 vector。供参考

// 注释版本
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1000010;
int primes[N] , cnt ;
bool st[N];

void get_primes(int n){
    for(int i = 2 ; i <= n ; i++ ){
        // 如果这个数没被筛掉，那么这个数为质数
        if(!st[i]) primes[cnt ++] = i;

        // 从小到大枚举所有的质数
        for(int j = 0 ; primes[j] <= n / i ; j ++){
            // 把当前质数和i的乘积筛掉
            st[ primes[j] * i] = true;      // 只用最小质因子来筛选
            if( i % primes[j] == 0) break;  // 当这句话发生的时候，说明primes[j]一定是i的最小质因子
            // 1. i % primes[j] == 0，此时，primes[j]一定是i的最小质因子，即 primes[j] 一定是 primes[j] * i 的最小质因子
            // 2. i % primes[j] != 0，primes[j] 一定小于i的所有质因子，即 primes[j] 一定是 primes[j] * i 的最小质因子
        }
    }
}

int main(){
    int n;
    cin >> n;
    get_primes(n);
    cout << cnt << endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

const int N = 1000010;
int cnt;
bool st[N];
vector<int> primes;

void get_primes(int n) {
    for (int i = 2; i <= n; i++) {
        if (!st[i])
            primes.push_back(i);

        for (int j = 0; primes[j] <= n / i; j++) {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0)
                break;
        }
    }
}

int main() {
    int n;
    cin >> n;

    get_primes(n);
    cout << primes.size() << endl;
}

备注：为什么线性筛法的时间复杂度这么低？

举一个例子：我们来筛选出 50 以内的质数。三个方法筛掉的数字为下图所示：

上图分别显示了方法 1~方法 3 在实际运算中的重复程度。可以发现，多余的时间复杂度其实全是因为重复遍历所导致的。而线性筛法真正做到了每个数只看一次，所以是的时间复杂度，非常的快。