c++费马素性测试

费马素性测试是一种快速判断一个数是否为质数的方法，它基于费马小定理，即对于所有的质数p和整数a，都有a^p ≡ a (mod p)。下面是一个C++实现的费马素性测试：

#include <iostream>
#include <cmath>
using namespace std;

bool is_prime(int n) {
    if (n < 2) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    int a = rand() % (n - 2) + 2;
    int p = n - 1;
    while (p % 2 == 0) {
        if (pow(a, p / 2) % n == n - 1) return true;
        p /= 2;
    }
    int res = pow(a, p) % n;
    return res == 1 || res == n - 1;
}

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

该函数先判断n是否小于2或为偶数，如果是则直接返回false。然后随机取一个整数a，如果a^(n-1) ≢ 1 (mod n)，则n一定不是质数，返回false。否则继续对n-1进行因式分解，如果存在一个因子p使得a^(p/2) ≡ -1 (mod n)，则n可能是质数，返回true。否则继续取一个随机数a，重复上述步骤，直到判断n为质数或执行一定次数后退出。