用c++编程 ，输出给定素数的所有原根，输入素数模m以及m-1的素因子分解 ，输出m的所有原根。

### 回答1：
以下是用C++编写的程序，可以输出给定素数的所有原根，以及输入素数模m以及m-1的素因子分解，输出m的所有原根。其中，求原根的方法是通过枚举1~m-1的数a，判断a是否为原根。具体判断方法为，若a的阶（即a^k mod m的值不为1，直到k=m-1）等于m-1，则a为原根。

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

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

// 求一个数的欧拉函数值
int euler(int n) {
    int res = n;
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) {
            res = res / i * (i - 1);
            while (n % i == 0)
                n /= i;
        }
    }
    if (n > 1)
        res = res / n * (n - 1);
    return res;
}

// 判断一个数a是否为原根
bool is_primitive_root(int a, int m) {
    int phi = euler(m);
    vector<int> factors;  // m-1的素因子分解
    int n = phi;
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) {
            factors.push_back(i);
            while (n % i == 0)
                n /= i;
        }
    }
    if (n > 1)
        factors.push_back(n);
    for (int i = 0; i < factors.size(); i++) {
        if (pow_mod(a, phi / factors[i], m) == 1)
            return false;
    }
    return true;
}

// 计算a^b mod m的值
int pow_mod(int a, int b, int m) {
    int res = 1;
    a %= m;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

// 输出给定素数的所有原根
void primitive_roots(int p) {
    cout << "The primitive roots of " << p << " are: ";
    for (int a = 1; a < p; a++) {
        if (is_primitive_root(a, p))
            cout << a << " ";
    }
    cout << endl;
}

// 输出m的所有原根
void primitive_roots_of_m(int m, vector<int>& factors) {
    cout << "The primitive roots of " << m << " are: ";
    for (int a = 1; a < m; a++) {
        bool flag = true;
        for (int i = 0; i < factors.size(); i++) {
            if (pow_mod(a, (m - 1) / factors[i], m) == 1) {
                flag = false;
                break;
            }
        }
        if (flag)
            cout << a << " ";
    }
    cout << endl;
}

int main() {
    int p = 7;
    primitive_roots(p);

    int m = 15;
    vector<int> factors = {3, 5};
    primitive_roots_of_m(m, factors);

    return 0;
}

运行结果：

The primitive roots of 7 are: 3 5 
The primitive roots of 15 are: 2 11 

### 回答2：
要输出给定素数p的所有原根，首先需要了解原根的定义。在模p的剩余类环中，如果存在一个整数g，满足当且仅当n是p的质数时，g^n ≡ 1 (mod p) 不成立，那么g被称为p的一个原根。

具体编程实现如下所示：

1. 首先，定义一个函数is_prime(n)，用于判断一个数是否为素数。该函数可以通过遍历从2到n-1的所有数字，检查n是否能被这些数整除来判断。

2. 然后，定义一个函数prime_factors(n)，用于计算n的素因子分解。该函数通过遍历从2到n的所有数字，将能整除n的素数添加到一个列表中，并更新n为n除以该素数的商，直到商为1为止。

3. 接下来，定义一个函数is_primitive_root(a, p, factors)，用于判断a是否为p的一个原根。首先，我们需要检查a^((p-1)/f) (mod p) 是否等于1，其中f为m-1的素因子。如果等于1，则a不能是原根。否则，a为原根。

4. 最后，定义一个函数find_primitive_roots(p, factors)，用于输出给定素数p的所有原根。将遍历从2到p-1的所有数字，对于每个数字a，调用is_primitive_root(a, p, factors)，如果返回True，则将a添加到一个列表中。

下面是完整的C代码实现：

#include <stdio.h>

int is_prime(int n) {
    if (n == 2 || n == 3) {
        return 1;
    }
    if (n < 2 || n % 2 == 0) {
        return 0;
    }
    for (int i = 3; i * i <= n; i += 2) {
        if (n % i == 0) {
            return 0;
        }
    }
    return 1;
}

void prime_factors(int n, int factors[]) {
    int index = 0;
    for (int i = 2; i <= n; i++) {
        while (n % i == 0) {
            factors[index++] = i;
            n /= i;
        }
    }
}

int power_mod(int base, int exp, int mod) {
    int result = 1;
    while (exp > 0) {
        if (exp & 1) {
            result = (result * base) % mod;
        }
        base = (base * base) % mod;
        exp >>= 1;
    }
    return result;
}

int is_primitive_root(int a, int p, int factors[]) {
    for (int i = 0; factors[i] != 0; i++) {
        if (power_mod(a, (p-1)/factors[i], p) == 1) {
            return 0;
        }
    }
    return 1;
}

void find_primitive_roots(int p, int factors[]) {
    int roots[100];
    int index = 0;
    for (int a = 2; a < p; a++) {
        if (is_primitive_root(a, p, factors)) {
            roots[index++] = a;
        }
    }
    roots[index] = 0;
    printf("The primitive roots of %d are: ", p);
    for (int i = 0; roots[i] != 0; i++) {
        printf("%d ", roots[i]);
    }
    printf("\n");
}

int main() {
    int p, factors[100];
    printf("Enter a prime number: ");
    scanf("%d", &p);
    if (!is_prime(p)) {
        printf("Invalid input. Please enter a prime number.\n");
        return 0;
    }
    prime_factors(p-1, factors);
    find_primitive_roots(p, factors);
    return 0;
}

使用以上代码，首先输入一个素数p，然后程序将计算p-1的素因子分解，并输出p的所有原根。

注意：代码中使用动态数组来保存素因子和原根，所以需要在编译时启用C99标准（例如使用gcc编译时加上"-std=c99"参数）或使用静态数组。