写一个用素性检验判断一个超过64位的数的C++代码

素性检验是一种用于判断一个数是否为素数的概率算法，它的正确性与素数的分布规律有关系。对于一个超过64位的数，我们可以使用 Miller-Rabin 算法来进行素性检验。下面是一个使用 Miller-Rabin 算法判断一个超过64位的数是否为素数的 C++ 代码：

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>

using namespace std;

// 快速幂算法
long long power(long long x, long long y, long long p) {
    long long res = 1;
    x %= p;
    while (y > 0) {
        if (y & 1)
            res = res * x % p;
        y >>= 1;
        x = x * x % p;
    }
    return res;
}

// Miller-Rabin 算法
bool miller_rabin(long long n, int k) {
    if (n <= 2 || n % 2 == 0)
        return (n == 2);
    long long s = n - 1;
    while (s % 2 == 0)
        s >>= 1;
    for (int i = 0; i < k; i++) {
        long long a = rand() % (n - 2) + 2;
        long long x = power(a, s, n);
        if (x == 1 || x == n - 1)
            continue;
        while (s > 1 && x != n - 1) {
            x = x * x % n;
            s >>= 1;
        }
        if (x != n - 1)
            return false;
    }
    return true;
}

// 判断一个数是否为素数
bool is_prime(long long n) {
    const int k = 10; // 进行 k 次测试
    for (int i = 0; i < k; i++) {
        if (!miller_rabin(n, 20))
            return false;
    }
    return true;
}

int main() {
    srand(time(NULL));
    long long n;
    cin >> n;
    if (is_prime(n))
        cout << "YES\n";
    else
        cout << "NO\n";
    return 0;
}

这个程序使用了快速幂算法来计算幂次，使用了 Miller-Rabin 算法进行素性检验。其中，miller_rabin 函数用于进行一次 Miller-Rabin 测试，is_prime 函数用于进行多次 Miller-Rabin 测试。