C语言实现输出素数n(如n=47)的所有原根
时间: 2024-12-22 13:27:23 浏览: 76
在C语言中,我们可以编写一段程序来找出给定整数n的所有原始根。原始根是指能够使得模幂运算结果等于1的较小正整数。以下是一个简单的示例,用于找到小于sqrt(n)的所有可能的原始根:
```c
#include <stdio.h>
#include <math.h>
// 检查是否为素数
int isPrime(int n) {
if (n <= 1)
return 0;
for (int i = 2; i * i <= n; i++) {
if (n % i == 0)
return 0;
}
return 1;
}
// 计算a对m的欧几里得逆元
int extendedEuclidean(int a, int m) {
int x, y, u, v;
int t, q;
x = 0; u = 1;
y = 1; v = 0;
while (a > 0) {
q = m / a;
t = a; a = m % a;
m = t; t = x; x = u - q * x;
u = t; t = y; y = v - q * y;
v = t;
}
return u % m;
}
// 输出所有小于n的原始根
void findPrimitiveRoots(int n) {
if (!isPrime(n)) {
printf("输入的数字不是素数\n");
return;
}
for (int i = 2; i < n && i * i < n; ++i) { // 只需检查到sqrt(n)
int phi = n - 1; // Eulers totient function
int inv = extendedEuclidean(i, phi);
if (inv != 1 && inv != phi - 1) {
int root = i * inv % n;
printf("%d 的原始根: %d\n", n, root);
}
}
}
int main() {
int n = 47;
findPrimitiveRoots(n);
return 0;
}
```
注意,这个程序仅适用于相对小的输入值,因为计算原始根可能会变得非常慢,尤其是对于大素数。此外,如果n有多个原始根,此代码只会打印出其中一个。
阅读全文
相关推荐
















