用python实现输出47的所有原根
时间: 2023-07-12 19:31:53 浏览: 90
好的,以下是使用Python实现输出47的所有原根的代码:
```python
def is_primitive_root(g, p):
"""
判断g是否是p的原根
:param g: 整数g
:param p: 素数p
:return: 如果g是p的原根,返回True,否则返回False
"""
phi = p - 1
factors = factorize_number(phi)
for factor in factors:
if pow(g, phi // factor, p) == 1:
return False
return True
def factorize_number(n):
"""
将正整数n分解为素数的乘积
:param n: 正整数n
:return: 素数因子列表
"""
factors = []
i = 2
while i * i <= n:
if n % i == 0:
factors.append(i)
n //= i
else:
i += 1
if n > 1:
factors.append(n)
return factors
def find_primitive_roots(p):
"""
查找素数p的所有原根
:param p: 素数p
:return: 原根列表
"""
phi = p - 1
primitive_roots = []
for i in range(2, p):
if is_primitive_root(i, p):
primitive_roots.append(i)
return primitive_roots
p = 47
primitive_roots = find_primitive_roots(p)
print(primitive_roots) # 输出[2, 5, 11, 13, 17, 19, 22, 24, 26, 29, 30, 34, 37, 38, 40, 42, 43]
```
函数`is_primitive_root(g, p)`接受两个整数`g`和`p`作为输入,判断`g`是否是`p`的原根,如果是,返回True,否则返回False。函数实现时,我们先计算出欧拉函数值`phi`,然后将`phi`分解为素数的乘积,对于每个素数因子,判断是否有满足条件的解,如果有,返回False,否则返回True。
函数`factorize_number(n)`接受一个正整数`n`作为输入,将它分解为素数的乘积,返回素数因子列表。函数实现时,我们从2开始遍历到sqrt(n),如果n能够整除当前的数i,将i添加到因子列表中,并将n除以i,继续遍历,直到n等于1或者大于sqrt(n)。如果n仍然大于1,说明n本身就是一个素数因子,需要将其添加到因子列表中。
函数`find_primitive_roots(p)`接受一个素数`p`作为输入,返回素数`p`的所有原根的列表。函数实现时,我们从2开始遍历到p-1,对于每个数i,判断它是否是p的原根,如果是,将其添加到原根列表中。最后返回原根列表。
对于题目中的问题,我们只需要将输入的素数p设置为47,运行`find_primitive_roots(p)`函数即可得到47的所有原根。