C++实现输出素数n的所有原根代码

在C++中，我们可以编写一个程序来找出给定正整数n的所有原始根。原始根是指能够生成其模意义下所有非平凡剩余类的最小正整数。以下是一个简单的示例，利用欧拉函数和循环来寻找原始根：

#include <iostream>
#include <vector>
using namespace std;

// 计算最大公约数
int gcd(int a, int b) {
    return (b == 0) ? a : gcd(b, a % b);
}

// 欧拉函数计算 φ(n)
int phi(int n) {
    int result = n;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            while (n % i == 0) {
                n /= i;
            }
            result -= result / i;
        }
    }
    if (n > 1) {
        result -= result / n;
    }
    return result;
}

// 判断是否为原始根
bool isPrimitiveRoot(int g, int n) {
    for (int x = 1; x < n && gcd(x, n) == 1; ++x) {
        if ((g pow mod x) % n == 1) {
            return false;
        }
    }
    return true;
}

// 找出所有原始根
void findPrimitiveRoots(int n) {
    vector<int> roots;
    for (int i = 2; i < n; ++i) {
        if (gcd(i, n) == 1 && isPrimitiveRoot(i, n)) {
            roots.push_back(i);
        }
    }
    cout << "原始根 of " << n << ": ";
    for (const auto &root : roots) {
        cout << root << " ";
    }
    cout << endl;
}

int main() {
    int n;
    cout << "请输入一个正整数: ";
    cin >> n;
    findPrimitiveRoots(n);
    return 0;
}

在这个代码中，我们首先计算欧拉函数φ(n)，然后遍历从2到n-1的所有整数，检查它们是否满足原始根的条件。如果找到一个原始根，就将其添加到结果向量中。注意这里的`pow`函数是自定义的，用于计算两个数相乘的幂运算。