Fermat素数测试，测试n（c++实现）

Fermat素数测试是利用费马小定理来判断一个数是不是素数。以下是C++实现Fermat素数测试的代码：

#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 fermat(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;
        if (pow_mod(a, n - 1, n) != 1) return false;
    }
    return true;
}

int main() {
    int n, times;
    cin >> n >> times;
    if (fermat(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$的结果，`fermat`函数用于判断$n$是否为素数，其中`times`表示随机测试的次数，可以根据需要进行调整。在主函数中，输入需要判断的数$n$和随机测试的次数`times`，输出判断结果。