下面是实现代码(此代码采用int保存所有数据)
#include
#include
#define MAX_NUM 500
using namespace std;
//判断一个数是否为素数
bool IsPrime(int n)
{
if (n == 1) return false;
if (n == 2) return true;
int sqrtn = (int)sqrt(n);
for (int i = 2; i < sqrtn + 1; i++)
if (n%i == 0) return false;
return true;
}
//如果数n是个素数,则直接添加到素因数数组pri_factor,并终止此函数。
//否则,从[2,∞]中寻得素数,将其添加到数组并除以n。
//求一个数n的素因数,返回数组大小
int PrimeFactor(int *pri_factor, int n)
{
int index = 0;//用于数组去重并记录数组大小
while (!IsPrime(n)){
for (int i = 2; i < n / 2 + 1; i++){
if (IsPrime(i)&&n%i==0){//找到一个素因数i
if (index > 0 && pri_factor[index - 1] == i)
index--;
pri_factor[index++] = i;
n /= i;
break;
}
}
}
if (index == 0)
pri_factor[index++] = n;
else if(n!=pri_factor[index-1])
pri_factor[index++] = n;
return index;
}
//a的e次幂(mod p)
int IntModPow(int a, int e, int p)
{
int factor = 1;//积
for (int i = 0; i < e; i++){
factor *= a;
if (factor > p)
factor %= p;
}
return factor;
}
//求某一原根
int OneRoot(int *pri_factor,int len_array,int p)
{
int g = 2;
int *q;
q = new int[len_array];
for (int i = 0; i < len_array; i++)
q[i] = (p - 1) / pri_factor[i];
for (int i = 0; i < 65535; i++){
//sign为1表示g的q[j]次幂模p同余1
int j,sign=0;
for (j = 0; j < len_array; j++){
//若g的q[j]次幂模p同余1,则不合定理
//跳过此g
if (IntModPow(g, q[j], p) == 1){
sign = 1;
break;
}
}
//遍历q[j],满足g的q[j]次幂模p不同余1,
//则说明g为原根
if (!sign&&j == len_array){
delete[]q;
return g;
}
g++;
}
//若原根未找到,则返回0
delete[]q;
return 0;
}
//求两个数的最大公约数
int GcdNum(int a, int b)
{
while (a != b){
if (a%b == 0)
return b;
if (b%a == 0)
return a;
if (a > b) a %= b;
else if (a < b) b %= a;
}
return a;
}
//求与n互素的d,返回数组大小
int RootE(int *d, int n)
{
int index = 0;
for (int i = 1; i < n; i++)
if (GcdNum(i, n) == 1)
d[index++] = i;
return index;
}
//主函数
int main()
{
int p;//模
int pri_factor[MAX_NUM];//素因数
int d[MAX_NUM];//原根的指数
while (1){
cin >> p;
int len_pri=PrimeFactor(pri_factor,p-1);
int one_root=OneRoot(pri_factor, len_pri, p);
if (one_root == 0){
cout << "未找到原根" << endl;
return 0;
}
int len_d = RootE(d, p - 1);
cout << "原根的个数:" << len_d << endl;
cout << "原根分别为:";
for (int i = 0; i < len_d; i++)
cout << IntModPow(one_root, d[i], p) << " ";
cout << endl;
}
return 0;
}
注:若有错误,欢迎大家在评论区指正。