C++实现输出素数n的所有原根代码及运行结果

在C++中，我们可以编写一个程序来找出素数`n`的所有原根。原根是指模一个质数p而言，它能整除(p-1)且满足对于任何正整数k，a^((p-1)/q) ≡ 1 (mod p)，其中q是p-1的最大质因数。以下是一个简单的示例，用于找到`n`的所有原根：

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

// Function to check if a number is prime
bool isPrime(int n) {
    if (n <= 1)
        return false;
    for (int i = 2; i * i <= n; ++i)
        if (n % i == 0)
            return false;
    return true;
}

// Function to find the primitive roots modulo n
std::vector<int> findPrimitiveRoots(int n) {
    std::vector<int> primitive_roots;
    if (!isPrime(n))
        return primitive_roots; // Not a prime, no primitive roots

    for (int a = 2; a < n; ++a) {
        bool is_root = true;
        int order = n - 1;

        while (order > 1 && is_root) {
            if (pow(a, order / gcd(order, n)) % n != 1) {
                is_root = false;
            }
            order = gcd(order, n);
        }

        if (is_root && order == n - 1)
            primitive_roots.push_back(a);
    }

    return primitive_roots;
}

// GCD function
int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

int main() {
    int n = 73; // Replace with your desired prime number
    std::vector<int> roots = findPrimitiveRoots(n);

    std::cout << "The primitive roots of prime number " << n << " are:\n";
    for (const auto &root : roots) {
        std::cout << root << "\n";
    }