Fermat素性检测算法c++代码，含安全参数k

Fermat素性检测算法是一种基于费马小定理的简单方法来判断一个数是否可能是质数。它不是一种高效算法，因为对于大数来说，更复杂的测试如Miller-Rabin更为可靠。然而，为了演示基本原理，以下是使用C++实现的一个简单的Fermat素性检验函数，包括安全参数k：

#include <iostream>
#include <vector>

// 检查n是否满足费马小定理
bool fermatTest(int n, int k) {
    if (n <= 1 || n == 4) return false; // 特殊情况处理
    for (int a = 2; a < n; ++a) { // 避免循环内除法，提高效率
        bool isComposite = true;
        for (int r = 0; r < k && isComposite; ++r) {
            int pow_result = static_cast<uint64_t>(a) * static_cast<uint64_t>(a) % n;
            if (pow_result == a) {
                isComposite = false;
            } else {
                pow_result *= pow_result;
                while (pow_result > n && r != k - 1) {
                    pow_result %= n;
                    ++r;
                }
                if (pow_result == a) {
                    isComposite = false;
                    break;
                }
            }
        }
        if (isComposite)
            return false;
    }
    return true;
}

int main() {
    int num = 17; // 输入要检测的数字
    int k = 5; // 安全参数，一般取大于2的偶数

    std::cout << "Checking if " << num << " is prime using Fermat's test with k=" << k << "..." << std::endl;
    if (fermatTest(num, k))
        std::cout << num << " seems to be a probable prime." << std::endl;
    else
        std::cout << num << " is composite according to the Fermat's test." << std::endl;

    return 0;
}