c++实现生成大素数(用费马素性测试，32位整数)

以下是使用费马素性测试生成32位大素数的C++代码：

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cmath>

using namespace std;

// 生成32位随机数
unsigned int rand32() {
    return rand() & 0xFFFF | rand() << 16;
}

// 检查n是否为素数
bool isPrime(unsigned int n) {
    if (n <= 1) {
        return false;
    }
    if (n == 2 || n == 3) {
        return true;
    }
    unsigned int s = sqrt(n);
    for (unsigned int i = 2; i <= s; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

// 费马素性测试
bool fermatTest(unsigned int n, int k) {
    if (n <= 1 || n == 4) {
        return false;
    }
    if (n <= 3) {
        return true;
    }
    while (k-- > 0) {
        unsigned int a = 2 + rand() % (n - 3);
        if (__gcd(a, n) != 1) {
            return false;
        }
        if (pow(a, n - 1) % n != 1) {
            return false;
        }
    }
    return true;
}

// 生成32位大素数
unsigned int generatePrime() {
    srand(time(NULL));
    unsigned int n;
    do {
        n = rand32();
    } while (!fermatTest(n, 5) || !isPrime(n));
    return n;
}

int main() {
    cout << "32位大素数：" << generatePrime() << endl;
    return 0;
}

该程序使用了费马素性测试检测是否为素数，同时也进行了简单的试除法判断。为了保证生成的素数质量，使用了随机数生成器生成随机数，并进行多次检测。如果检测不通过，则重新生成随机数直到满足要求。