Solovay-Strassen素性测试，测试n（c++实现）

Solovay-Strassen素性测试是利用二次剩余的性质来判断一个数是不是素数。以下是C++实现Solovay-Strassen素性测试的代码：

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

// 计算a^b mod n的结果
int pow_mod(int a, int b, int n) {
    int ans = 1;
    a %= n;
    while (b) {
        if (b & 1) ans = (long long)ans * a % n;
        b >>= 1;
        a = (long long)a * a % n;
    }
    return ans;
}

// 判断n是否为素数，是素数返回true，否则返回false
bool solovay_strassen(int n, int times) {
    if (n == 2) return true;
    if (n < 2 || n % 2 == 0) return false;
    srand((unsigned)time(NULL));
    for (int i = 0; i < times; i++) {
        int a = rand() % (n - 2) + 2;
        int x = pow_mod(a, (n - 1) / 2, n);
        if (x == 0 || x == 1 || x == n - 1) continue;
        int flag = 0;
        for (int j = 1; j < n - 1; j <<= 1) {
            x = (long long)x * x % n;
            if (x == n - 1) {
                flag = 1;
                break;
            }
        }
        if (flag == 0) return false;
    }
    return true;
}

int main() {
    int n, times;
    cin >> n >> times;
    if (solovay_strassen(n, times)) cout << n << " is a prime number." << endl;
    else cout << n << " is not a prime number." << endl;
    return 0;
}

在上述代码中，`pow_mod`函数用于计算$a^b \mod n$的结果，`solovay_strassen`函数用于判断$n$是否为素数，其中`times`表示随机测试的次数，可以根据需要进行调整。在主函数中，输入需要判断的数$n$和随机测试的次数`times`，输出判断结果。