c++求大素数原根的代码函数

以下是一个 C++ 函数，它可以用于计算大素数的原根：

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

using namespace std;

// 判断一个数是否为素数
bool is_prime(int n) {
    if (n <= 1) {
        return false;
    }
    int sqr = sqrt(n);
    for (int i = 2; i <= sqr; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

// 计算 a 的 b 次方对 p 取模的结果
int power_mod(int a, int b, int p) {
    int res = 1;
    while (b) {
        if (b & 1) {
            res = (long long)res * a % p;
        }
        a = (long long)a * a % p;
        b >>= 1;
    }
    return res;
}

// 获取大素数 p 的原根
int get_primitive_root(int p) {
    if (!is_prime(p)) {
        return -1;
    }
    vector<int> factors;
    int phi = p - 1;
    int tmp = phi;
    for (int i = 2; i <= tmp / i; i++) {
        if (tmp % i == 0) {
            factors.push_back(i);
            while (tmp % i == 0) {
                tmp /= i;
            }
        }
    }
    if (tmp > 1) {
        factors.push_back(tmp);
    }
    for (int g = 2; g <= p; g++) {
        bool flag = true;
        for (int i = 0; i < factors.size(); i++) {
            if (power_mod(g, phi / factors[i], p) == 1) {
                flag = false;
                break;
            }
        }
        if (flag) {
            return g;
        }
    }
    return -1;
}

int main() {
    int p;
    cout << "请输入一个大素数 p：" << endl;
    cin >> p;
    int g = get_primitive_root(p);
    if (g == -1) {
        cout << "无法找到 " << p << " 的原根！" << endl;
    } else {
        cout << p << " 的一个原根为：" << g << endl;
    }
    return 0;
}

该函数首先判断输入的 p 是否为素数，如果不是，则输出错误信息并返回 -1。接着，它将 p - 1 分解为质因数的积，并逐个尝试每个可能的原根。对于每个可能的原根 g，它计算 g 的 phi(p) / factors[i] 次方对 p 取模的结果，并检查是否等于 1。如果对于所有质因子 i，g 的 phi(p) / factors[i] 次方对 p 取模的结果都不等于 1，则 g 是 p 的原根。如果无法找到 p 的原根，则输出错误信息并返回 -1。

注意，计算原根的时间复杂度为 O(p log^2 p)，因此该函数对于较大的素数可能需要较长的计算时间。