素数是什么？

首先，我们要明白什么是素数。素数就像是一个特殊的密码，它只能被1和它自己整除。比如2、3、5、7等，它们都只能被1和它们自己整除。

米勒-拉宾测试是什么？

米勒-拉宾测试就像是一个游戏，用来检查一个数是不是素数。我们可以把这个游戏想象成一种特殊的“石头剪刀布”，但是规则有点复杂。

游戏规则：

1. 选择一个数：首先，我们选一个数 n ，我们要检查这个数是不是素数。
2. 数的变身：然后，我们把 ?1n?1 变成2的倍数。比如，如果 ?1n?1 是5，我们可以把它写成 2×2+12×2+1 ，这里的2就是我们要翻倍的次数，1就是剩下的不能再被2整除的部分。
3. 选择一个助手：我们再选一个助手 a ，这个助手可以是2到 n?1之间的任何数。
4. 开始游戏：我们用助手a 和数 n 来玩游戏。游戏的第一步是把助手 a乘以自己 d 次（d 是我们之前找到的那个不能再被2整除的部分）。然后，我们继续把结果再乘以自己，重复 r 次（r是我们之前翻倍的次数）。
5. 检查结果：每次乘完后，我们都要看结果是不是变成了1或者 n?1。如果是，那么我们继续游戏；如果不是，我们就要特别小心了。
6. 完成游戏：如果我们在 r 次游戏后，结果既不是1也不是 n?1，那么我们认为 n 可能不是素数。
7. 多次尝试：为了确保我们的判断是正确的，我们可以换不同的助手a 再玩几次游戏。如果每次游戏的结果都告诉我们 n 不是素数，那么我们就可以比较确定 n 真的不是素数。
8. 可能是素数：如果不管我们怎么换助手 a 玩游戏，结果都告诉我们n是素数，那么我们就可以认为 n 可能是素数。

米勒-拉宾测试就像是一个反复验证的游戏，通过不同的助手a 来检查一个数n是否是素数。虽然这个方法不能100%保证n 就是素数，但只要我们玩得次数足够多，就可以非常接近真相。

C++程序实现：

#include <iostream>
#include <vector>
#include <random>
#include <ctime>

using namespace std;

// 计算最大公约数
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

// 执行米勒-拉宾素性测试的辅助函数
bool millerRabinTest(long long d, long long a, long long n) {
    long long x = pow(a, d, n); // 计算 a^d % n

    if (x == 1 || x == n - 1)
        return true;

    while (d != n - 1) {
        d *= 2;
        x = (x * x) % n; // 计算 x^2 % n

        if (x == n - 1)
            return true;
    }
    return false;
}

// 米勒-拉宾素性测试
bool isPrime(long long n, int iterations = 5) {
    if (n <= 1 || n == 4)
        return false;
    if (n <= 3)
        return true;

    long long d = n - 1;
    while (d % 2 == 0)
        d /= 2;

    random_device rd;
    mt19937_64 eng(rd());
    uniform_int_distribution<long long> distr(2, n - 2);

    for (int i = 0; i < iterations; i++) {
        long long a = distr(eng);
        if (!millerRabinTest(d, a, n))
            return false;
    }
    return true;
}

int main() {
    cout << "Enter a number to test if it's a prime: ";
    long long number;
    cin >> number;

    if (isPrime(number)) {
        cout << number << " is probably a prime number." << endl;
    } else {
        cout << number << " is not a prime number." << endl;
    }

    return 0;
}