实现输出素数n（如n=47）的所有原根c/c++

在C++中，要实现输出素数n的所有原根，你需要先确认n是否是质数，然后遍历从2到n-1的所有数，检查它们是否是n的原根。下面是一个简单的示例代码：

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

// 判断一个数是否为质数
bool isPrime(int num) {
    if (num <= 1) return false;
    for (int i = 2; i * i <= num; ++i) {
        if (num % i == 0) return false;
    }
    return num > 1;
}

// 计算并返回a对n的欧拉函数值（φ(n)）
int euler_phi(int a, int n) {
    int result = n;
    for (int i = 2; i * i <= a; ++i) {
        if (a % i == 0) {
            if (n % i == 0) {
                while (n % i == 0) n /= i;
                result /= i;
            }
        }
    }
    if (n > 1 && a % n == 0) {
        result /= n;
    }
    return result;
}

// 检查a是否为n的原根
bool isPrimitiveRoot(int a, int n) {
    return euler_phi(a, n) == n - 1;
}

// 输出素数n的所有原根
void printPrimitiveRoots(int n) {
    if (!isPrime(n)) {
        cout << n << " is not a prime number, cannot find its primitive roots.\n";
        return;
    }

    vector<int> roots;
    for (int a = 2; a < n; ++a) {
        if (isPrimitiveRoot(a, n))
            roots.push_back(a);
    }

    cout << "Primitive roots of prime " << n << ": ";
    for (const auto &root : roots)
        cout << root << " ";
    cout << endl;
}

int main() {
    int n = 47;
    printPrimitiveRoots(n);
    return 0;
}

这个程序首先判断n是否是质数，如果是，则找出所有小于n的原根，并打印出来。如果n不是质数，则输出相应的提示。

请注意，寻找大的质数原根可能会非常耗时，特别是当n较大时。在这个例子中，我们仅考虑了小于n的数作为原根候选，实际应用中可能需要优化算法。