费马素性检验算法编写c程序

马素性检验算法是一种判断一个数是否为素数的算法，下面是用C++语言编写的费马素性检验小工具的代码：

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

long long quickPow(long long a, long long b, long long mod) {
    long long ans = 1;
    while (b) {
        if (b & 1) ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}

bool Miller_Rabin(long long n, int k) {
    if (n == 2) return true;
    if (n < 2 || !(n & 1)) return false;
    long long d = n - 1;
    int s = 0;
    while (!(d & 1)) {
        s++;
        d >>= 1;
    }
    srand(time(NULL));
    for (int i = 0; i < k; i++) {
        long long a = rand() % (n - 2) + 2;
        long long x = quickPow(a, d, n);
        if (x == 1 || x == n - 1) continue;
        for (int j = 1; j < s; j++) {
            x = x * x % n;
            if (x == n - 1) break;
        }
        if (x == n - 1) continue;
        return false;
    }
    return true;
}

int main() {
    long long n;
    int k;
    cout << "请输入要检测的大整数n：";
    cin >> n;
    cout << "请输入选定的安全系数k：";
    cin >> k;
    if (Miller_Rabin(n, k)) {
        cout << n << "可能是素数" << endl;
    } else {
        cout << n << "是合数" << endl;
    }
    return 0;
}