首页输出素数47的所有原根c++代码

输出素数47的所有原根c++代码

时间: 2024-12-24 13:00:56 浏览: 55

在C++中，我们可以编写一个程序来找出给定数47的所有原根。原根是一个整数a，满足对于模n来说，a的若干次幂能够生成所有小于n且与n互质的非负整数。以下是简单的代码示例： ```cpp #include <iostream> #include <vector> using namespace std; // 判断是否为素数 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; } // 计算模n下的欧拉函数φ(n) int phi(int n) { int result = n; for (int i = 2; i * i <= n; ++i) { if (n % i == 0) { result -= result / i; while (n % i == 0) n /= i; } } if (n > 1) result -= result / n; return result; } // 检查数字a是否为47的原根 bool findPrimitiveRoot(int a, int n) { if (gcd(a, n) != 1 || !isPrime(n)) return false; int order = phi(n); for (int i = 1; i <= order; ++i) { if ((a pow i) % n == 1) return i == order; } return false; } // 找出47的所有原根 void findPrimitiveRoots(int n) { vector<int> roots; for (int a = 2; a < n; ++a) { if (findPrimitiveRoot(a, n)) { roots.push_back(a); } } if (!roots.empty()) cout << "47的原根有: "; else cout << "47没有原根.\n"; for (int root : roots) cout << root << " "; cout << endl; } int main() { int num = 47; if (isPrime(num)) findPrimitiveRoots(num); else cout << num << "不是素数.\n"; return 0; } // 相关问题-- 1. 这段代码如何检测一个数字是否为47的原根？ 2. `gcd` 函数在这里的作用是什么？ 3. 如果47不是一个素数，这段代码会怎么处理？

阅读全文