素数

最近更新于 5月 5, 2024 2 分钟阅读时长算法与数据结构

素性测试

素数：若整数 $n ( n > 1)$ 只有 $1$ 和 $n$ 两个因数，则 $n$ 为素数。

试除法

判断一个数 $n$ 是否为素数，最直接的办法是按照定义判断，依次看 $2,3,\cdots,n-1$ 能否整除 $n$，若能整除则 $n$ 为合数，都不能整除则 $n$ 为素数，算法时间复杂度为 $O(n)$。

 1// 素性测试
 2bool isPrime(int n) {
 3    if (n < 2) {
 4        return false;
 5    } else {
 6        for(int i = 2; i < n - 1; i++) {
 7            if (n % i == 0) {
 8                return false;
 9            }
10        }
11        return true;
12    }
13}

若 $n$ 为合数，则 $\exists s \geq t \in N_{+} 且 s \geq t > 1$ 使得 $n = st$，于是有 $t \leq \sqrt{n}$，也就是说合数 $n$ 一定存在一个因数小于等于 $\sqrt{n}$。因此我们只需要对 $2,3,\cdots,\sqrt{n}$ 判断是否能整除 $n$ 即可。因此上述算法时间复杂度可降为 $O(\sqrt{n})$.

 1// 素性测试
 2bool isPrime(int n) {
 3    if (n < 2) {
 4        return false;
 5    } else {
 6        for (int i = 2; i * i <= n; i++) {
 7            if (n % i == 0) {
 8                return false;
 9            }
10        }
11        return true;
12    }
13}

打印素数表

Eratosthenes 筛法

算法思想是用已知素数的倍数去过滤掉那些合数，算法复杂度为 $O(n \log{\log n})$.

 1#include <vector>
 2
 3using namespace std;
 4
 5// Eratosthenes 筛法返回小于等于 n 的素数表
 6vector<int> eratosthenes(int n) {
 7    vector<int> primes;
 8    if (n < 2) {
 9        return primes;
10    }
11    vector<int> check(n + 1);
12    for (int i = 2; i <= n; i++) {
13        if (!check[i]) {
14            primes.push_back(i);
15            for (int j = 2 * i; j <= n; j += i) {
16                check[j] = true;
17            }
18        }
19    }
20    return primes;
21}

Euler 筛法

Euler 筛法也称线性筛法，时间复杂度为 $O(n)$.

 1#include <vector>
 2
 3using namespace std;
 4
 5// Euler 筛法
 6vector<int> euler(int n) {
 7    vector<int> primes;
 8    if (n < 2) {
 9        return primes;
10    }
11    vector<int> check(n + 1);
12    for (int i = 2; i <= n; i++) {
13        if (!check[i]) {
14            primes.push_back(i);
15        }
16        for (int j = 0; j < primes.size() && i * primes[j] <= n; j++) {
17            check[i * primes[j]] = true;
18            if (i % primes[j] == 0) {
19                break;
20            }
21        }
22    }
23    return primes;
24}

素因子分解

 1#include <vector>
 2
 3using namespace std;
 4
 5// 素因子分解: 试除法
 6vector<pair<int, int>> getPrimeFactorization(int n) {
 7    // factorization[i][0] 和 factorization[i][1] 表示第 i 个素因子及其指数
 8    // 素因子从小到达排序
 9    vector<pair<int, int>> factorization;
10    for (int i = 2; i * i <= n; ++i) {
11        if (n % i == 0) {
12            int index = 0;
13            while (n % i == 0) {
14                n /= i;
15                ++index;
16            }
17            factorization.emplace_back(i, index);
18        }
19    }
20    if (n != 1) {
21        factorization.emplace_back(n, 1);
22    }
23    return factorization;
24}

算法