费马素性检测算法C++代码

费马素性检测算法主要用于判断一个数是否可能是合数，即能否表示为两个大于1的整数之积。最著名的用于此目的的是Miller-Rabin素性测试，它是一种概率算法，而不是确定性的。以下是一个简单的C++代码示例，展示了如何使用Miller-Rabin算法：

#include <iostream>
#include <vector>
#include <cmath>

// 计算n的阶乘模m
int factorial(int n, int m) {
    if (n == 0 || n == 1)
        return 1;
    int result = 1;
    for (int i = 2; i <= n; ++i) {
        result = (result * i) % m;
    }
    return result;
}

// Miller-Rabin测试函数
bool isProbablePrime(int n, int k) {
    // 检查小于2的情况
    if (n <= 1)
        return false;

    // 如果n是2或3，它是素数
    if (n == 2 || n == 3)
        return true;

    // n必须是偶数
    if (n % 2 == 0)
        return false;

    // 写成2^r * d的形式，其中d是奇数
    int r = 0, d = n - 1;
    while (d % 2 == 0) {
        r++;
        d /= 2;
    }

    // 进行k次随机测试
    for (int i = 0; i < k; ++i) {
        int a = rand() % (n - 3) + 2; // 随机选择一个小于n-2的数
        int x = modular_exponentiation(a, d, n);

        // 如果x == 1 或 x == n-1，直接通过测试
        if (x == 1 || x == n - 1)
            continue;

        // 对于每个r次方，尝试找到x^(2^j) = -1 mod n
        bool witnessFound = false;
        for (int j = 0; j < r && !witnessFound; ++j) {
            x = (x * x) % n;
            if (x == n - 1) {
                witnessFound = true;
                break;
            }
        }

        // 如果所有可能都没有找到-witness，返回false
        if (!witnessFound)
            return false;
    }

    // 未发现反证，认为是素数
    return true;
}

// 计算a的b次方模n
int modular_exponentiation(int a, int b, int n) {
    int res = 1;
    while (b > 0) {
        if (b & 1)
            res = (res * a) % n;
        a = (a * a) % n;
        b >>= 1;
    }
    return res;
}

int main() {
    int num;
    std::cout << "Enter a number to test for primality: ";
    std::cin >> num;
    int tests = 5; // 可以调整测试次数增加可靠性

    if (isProbablePrime(num, tests))
        std::cout << num << " is probably prime.\n";
    else
        std::cout << num << " is composite or has a small divisor.\n";

    return 0;
}

注意这只是一个基础版本的示例，实际应用中可能需要处理更多的边界条件和优化。此外，`rand()` 函数在此处只做演示，生产环境应使用更安全的随机数生成器。