The secret of being a bore is to tell everything

0%

素数判定

定义:对于一个大于$1$的正整数$p$,如果$p$是质数/素数,那么对于所有$a|p$,$a$要么是$1$,要么是$p$。

那么对于一个数$x$,我们如何让计算机去判定它是不是质数/素数呢?

素数判定

朴素方法

根据定义,我们只需要判断这个数$x$,除了$1$和$x$以外还有没有其他约数就好了。

1
bool isPrime(ll x) {
2
    if (x < 2) return false;
3
    for (ll i = 2; i < x; i++) 
4
        if (x % i == 0) return false;
5
    return true;
6
}

这个算法的时间复杂度是$O(n)$,在极端情况下,$x$是质数的时候就需要扫遍$2~x$之间的所有值。但是实际上,我们并不需要扫到$x$,为什么呢?

考虑当$x$有一个约数$a$,$a|x$,那么一定有$\frac{x}{a}|x$。也就是说,每个约数都是对称的,对称中心就是$\sqrt{x}$。当$a\leq \sqrt{x}$存在一个对于$x$的约数的时候,$a > \sqrt{x}$一定也存在一个$\frac{x}{a}$,反之则不存在。所以我们只需要扫到$\sqrt{x}$就可以了。

1
bool isPrime(ll x) {
2
    if (x < 2) return false;
3
    for (ll i = 2; i * i <= x; i++) 
4
        if (x % i == 0) return false;
5
    return true;
6
}

这个算法的时间复杂度是$O(\sqrt{n})$,还不错。

筛法

但是在算法竞赛里面,经常有一类问题需要你对给出的$Q$个查询进行回答。此时如果查询范围很大,而次数又很多的话,上面的方法就会超时。

这时候就引出我们的埃氏筛/线性筛法。我们不从$x$出发去判断$x$是不是质数,而是从比较小的数开始,依次划掉这个数的倍数。因为质数的倍数一定不是质数(都有倍数了还怎么是质数),那么没有划掉的就是质数,直接$O(1)$判定即可。实现也非常简单

1
bool notprime[MAXN];
2
void sieve(int maxn) {
3
    for (int i = 2; i <= maxn; i++) {
4
        if (notprime[i]) continue;
5
        for (int j = i * 2; j <= maxn; j += i) notprime[j] = true;
6
    }
7
}

我之所以把数组定义成notprime是因为这样就不用把数组都初始化为$1$了。
这个算法的时间复杂度是多少呢?我们可以这样考虑,只有质数会进入第二个循环,而它会划掉所有它的倍数。那么也就是说,每个数最多会被划掉质因数个数那么多次。我们把一个数的质因数分解表示为$\prod_{k} p_k^{\alpha_k}$,则极端情况下,假设有$k$个不同质因数,则$n$的范围会是$2\times 3\times \dots \times p_k \geq k!$。而$k!$根据斯特林公式有
$$
n! \approx \sqrt{2\pi n}\bigg(\frac{n}{e}\bigg)^n \leq n^n
$$
那么$k$相对于$n$就是$O(\log{\log{n}})$级别的了,所以总复杂度是$O(n\log{\log{n}})$。这个复杂度与线性几乎没有差别了,虽然还有更高级的$O(n)$线性筛,但是这不是重点。

Miller–Rabin 素性测试

Miller-Rabin 素性测试是一个更高级的素数判定算法,为什么叫素性测试呢?因为这个算法也很难保证一定能测出这个数是不是质数,只能说它很像质数,有多像呢?非常非常像。

但是对于算法竞赛的数据范围来说,这个算法是可以准确判定出这个数是不是质数的。

Fermat小定理

如果$p$是质数,对于一个数$a \in [1, p-1]$,有
$$
a^{p-1} \equiv 1\pmod{p}
$$

如果我们想知道$n$是否是素数,我们在中间选取$a$,看看上面等式是否成立。如果$a^{n-1} \not\equiv 1\pmod{n}$,那么$n$一定不是质数。但是注意,这个定理的逆命题不一定成立,也就是说,$a^{n-1} \equiv 1\pmod{n}$不一定表示$n$是质数。

1
bool fermat(int n) {
2
    if (n < 3) return n == 2;
3
    for (int i = 1; i <= TEST_TIME; ++i) {
4
        int a = rand() % (n - 2) + 2;
5
        // 快速幂求得a^{n-1}
6
        if (fastExp(a, n - 1, n) != 1) return 0;
7
    }
8
    return 1;
9
}

事实上,有一类数满足

$n$是合数,对于与$n$互质的数$b$,$b^{n-1}\equiv 1\pmod{n}$

这样的数被称为Carmichael数,是费马测试的大敌,但是由于Carmichael比质数少得多,所以仍然有方法去应对它。它的一个等价定义:

一个正合成数$n$是卡迈克尔数,当且仅当$n$无平方数约数且对于所有$n$的素因数$p$,$p-1|n-1$。

二次探测定理

假设我们有$x^2 \equiv 1\pmod{p}$,$p$为素数,那么该式子可以化为
$$
(x - 1)(x + 1) \equiv 0\pmod{p}
$$
那么$p$能整除$(x - 1)(x + 1)$,此时$(x-1)$或者$(x+1)$能被质数$p$整除,有$x \equiv 1\pmod{p}$或者$x\equiv-1\pmod{p}$。

那么我们假设$n>2$是个质数,那么它一定是个奇数,且$n-1$一定可以被写成$d2^s$的形式,其中$s$是正整数,$d$是奇数。根据费马小定理,那么就有$a^{d2^s} \equiv1\pmod{n}$,同时,根据以上性质,对于$i \in [1, s-1]$,有
$$
a^{d2^i} \equiv-1\pmod{n}\\
a^d \equiv 1\pmod{n}
$$
所以我们可以不断对$a^{n-1}$取平方根后,判断是否出现不符合以上性质的根就知道它是否像质数了。同样,这个引理的逆命题也存在反例,但是由于Carmichael数的性质,它通不过平方探测,所以与费马小定理结合起来效果很不错。

但是即使这样,我们也只能说像是质数,事实上Miller–Rabin有$4^{-k}$的错误率,$k$是选取的基数$a$的数量。好消息是,在算法竞赛范围内$n\leq2^{64}$,选取$8$个素数作为基数就可以准确判定了。

时间复杂度:算法竞赛内用__int128_t可以达到$O(k\log{n})$,但是对于大整数一般是$O(k\log^3{n})$,可以用$FFT$优化到$O(k\log^2{n}\log{\log{n}}\log{\log{\log{n}}})$。

1
inline ll modmul(ll a, ll b, ll p) { return (__int128_t)a * (__int128_t)b % p; }
2
inline ll fastExp(ll x, ll p, ll mod) {
3
    x %= mod;
4
    ll ans = 1;
5
    while (p) {
6
        if (p & 1) ans = modmul(ans, x, mod);
7
        x = modmul(x, x, mod);
8
        p >>= 1;
9
    }
10
    return ans;
11
}
12
inline bool miller_rabin(ll x) {
13
    if (x == 2 || x == 3) return true;
14
    if (x < 2 || !(x & 1)) return false;
15
    ll pow = 0, u = x - 1;
16
    while (!(u & 1)) {
17
        pow++;
18
        u >>= 1;
19
    }
20
    for (int i = 0; i < 8; i++) {
21
        int p = primes[i];
22
        if (p >= x) break;
23
        ll v = fastExp(p, u, x);
24
        if (v == 1 || v == x - 1) continue;
25
        int j = 0;
26
        for (; j < pow; j++) {
27
            v = modmul(v, v, x);
28
            if (v == x - 1) break;
29
        }
30
        if (j == pow) return false;
31
    }
32
    return true;
33
}

例题:质数判定