Miller-Rabin 素数测试算法是一种能够快速检验一个数是否为素数的算法。

算法流程

费马小定理：如果 $n$ 为素数，那么对于 $\forall 1 \le a \le n - 1$，都有 $a^{n - 1} \equiv 1 \bmod n$。

二次探测法：如果 $n$ 为素数，那么方程 $a^2 \equiv 1 \bmod n$ 只有两个解：$a_1 = 1, a_2 = n - 1$。

于是我们可以设计一个算法，对于一个特定的 $a$ 来检验。

现将 $n - 1$ 表示成 $n - 1 = 2^d \times r$ 的形式，其中 $r$ 为奇数。那么我们依次检验 $a^r, a^{2r}, a^{4r}, \cdots, a^{2^d \times r}$ 是否为 $1$ 或 $n - 1$。如果没有一个数是 $1$ 或 $n - 1$，那么 $n$ 一定不是素数。

注意如果满足上述性质，那么 $n$ 不一定是素数；但是如果不满足，$n$ 一定不是素数。所以我们要进行多次检验。

检验需知

在 int 范围内，只需检验 $2, 7, 61$ 即可保证正确性。
在 long long 范围内，只需检验 $2, 325, 9375, 28178, 450775, 9780504, 1795265022$。
当 $n \le 4 \times 10^{13}$ 时，只需检验 $2, 2570940, 211991001, 3749873356$。
当 $n \le 3 \times 10^{15}$ 时，只需检验 $2, 2570940, 880937, 610386380, 4130785767$。

代码实现

1	#include <cstdio>
2
3	typedef long long ll;
4	int T;
5	ll n;
6
7	inline ll mult(const ll &x, const ll &y, const ll &n) {
8	return (__int128) x * y % n;
9	}
10
11	ll _pow(ll a, ll b, ll n) {
12	ll c = 1;
13	for (; b; b >>= 1, a = mult(a, a, n)) {
14	if (b & 1) c = mult(a, c, n);
15	}
16	return c;
17	}
18
19	bool miller(ll m, ll d, ll r, ll n) {
20	if (m > n - 2) return true;
21	ll x = _pow(m, d, n);
22	if (x == 1 \|\| x == n - 1) return true;
23	for (int i = 0; i < r; i++) {
24	x = mult(x, x, n);
25	if (x == n - 1) return true;
26	}
27	return false;
28	}
29
30	bool is_prime(ll n) {
31	if (n <= 2) return n == 2;
32	static ll m[] = { 2, 325, 9375, 28178, 450775, 9780504, 1795265022 };
33	ll d = n - 1, r = 0;
34	while (~d & 1) d >>= 1, r++;
35	for (int i = 0; i < 7; i++) {
36	if (!miller(m[i], d, r, n)) return false;
37	}
38	return true;
39	}
40
41	int main() {
42	scanf("%d", &T);
43	while (T--) {
44	scanf("%lld", &n);
45	printf("%s\n", is_prime(n) ? "Yes" : "No");
46	}
47	return 0;
48	}