用C++程序输出所有47的质数原根

在C++中，我们可以编写一个函数来找出给定数字的所有质数原根。首先需要明确的是，一个数n的质数原根是一个整数a，满足a的模n次方等于1，即a^k % n = 1，其中k是n的欧拉函数φ(n)（Euler's totient function）。对于质数p，它的φ值就是p - 1，因为对于任意a coprime to p（与p互质），都有a^(p-1) ≡ 1 (mod p)。

以下是实现该功能的一个简单示例：

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

// Function to check if a number is prime
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;
}

// Function to find primitive roots of a given prime number
void findPrimitiveRoots(int p) {
    vector<int> roots;
    for (int a = 2; a < p; ++a) { // Start from 2 as it's the smallest possible root
        bool found = true;
        int k = p - 1;
        while (true) {
            if ((a ** k) % p != 1) {
                found = false;
                break;
            }
            k *= 2;
            if (k >= p) break;
        }
        if (found && isPrime(a)) roots.push_back(a);
    }
    cout << "Primitive roots of " << p << ": ";
    for (const auto& root : roots)
        cout << root << " ";
    cout << endl;
}

int main() {
    int num = 47;
    if (isPrime(num)) {
        findPrimitiveRoots(num);
    } else {
        cout << "The number provided is not prime." << endl;
    }
    return 0;
}

这个程序会找到数字47的所有质数原根，如果输入的不是质数则输出提示信息。运行此程序，你会看到结果以及是否有47的质数原根。