跳转至

检查质数

试除法

以下代码提供几种时间复杂度上以及常数上的优化：

  • 试除到 \(\sqrt{n}\) 即可；
  • 提前判断是否是 \(2\) 或 \(3\) 的倍数，每次试除的对象为 \(6k \pm 1, k \in \mathbb{N}\)。
1
2
3
4
5
6
7
8
bool isPrime(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (int i = 5; i * i <= n; i += 6)
        if (n % i == 0 || n % (i + 2) == 0) return false;
    return true;
}

威尔逊定理

实际用处不大。

威尔逊定理

一个正整数是质数当且仅当 \((p-1)! \equiv -1 \pmod p\)。

1
2
3
4
5
6
7
8
bool is_prime(lli n) {
    if (n < 2) return false;
    lli fac = 1;
    for (lli i = 2; i < n; ++i) {
        fac = (fac * i) % n;
    }
    return fac == n - 1;
}

Miller–Rabin 素性测试

from © OI Wiki

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
bool millerRabin(int n) {
    if (n < 3 || n % 2 == 0) return n == 2;
    if (n % 3 == 0) return n == 3;
    int u = n - 1, t = 0;
    while (u % 2 == 0) u /= 2, ++t;
    // test_time 为测试次数，建议设为不小于 8
    // 的整数以保证正确率，但也不宜过大，否则会影响效率
    for (int i = 0; i < test_time; ++i) {
        // 0, 1, n-1 可以直接通过测试, a 取值范围 [2, n-2]
        int a = rand() % (n - 3) + 2, v = quickPow(a, u, n);
        if (v == 1) continue;
        int s;
        for (s = 0; s < t; ++s) {
            if (v == n - 1) break;    // 得到平凡平方根 n-1，通过此轮测试
            v = (long long)v * v % n;
        }
        // 如果找到了非平凡平方根，则会由于无法提前 break; 而运行到 s == t
        // 如果 Fermat 素性测试无法通过，则一直运行到 s == t 前 v 都不会等于 -1
        if (s == t) return 0;
    }
    return 1;
}

其他方法

见 素数 - OI Wiki