python求素数因子-Python入门教程：素数判断与素因子分解.pdf
139 浏览量
2023-06-12
13:16:33
上传
评论
收藏 84KB PDF 举报
python求素数因⼦_Python⼊门教程：素数判断与素因⼦分解
好了, 我们继续挑战下Python⼊门编程, 如何判断⼀个数是素数？以及如何分解⼀个合数？
⾸先回忆下：素数就是⼤于1且除了1和它本⾝之外没有其他素因⼦。⼤于1的⾮素数称为合数。形如F_n=2^2^n+1的数称为Fermat数。
本节将判断Fermat数是否是素数。
isprime函数
# -*- coding: utf-8 -*-
def isprime(num: int) -> bool:
if not isinstance(num, int):
raise TypeError
if num < 0:
num = -num
if num == 1:
return False
if num == 2:
return True
if not num % 2:
return False
p = 3
while p * p <= num:
if not num % p:
return False
else:
p += 2
return True
这⾥⽤到了定义函数时, 进⾏输⼊参数的类型判断。 想⼀想, 如何添加输出参数的类型判断。
接下来, 我么将负数转化为正数, ⽽对1,2这两个特例进⾏简单处理。最后⽤⼀个while循环来从p=3开始判断p是不是其素因⼦, 如果是则返
回⾮素数, 否则对p+2再次循环判断, 直到p*p超过要判断的数为⽌。
对Fermat数是否为素数可以测试如下。
# test with Fermat numbers
for i in range(7):
print(2**2**i + 1, isprime(2**2**i + 1))
素因⼦分解
从上⾯可以看到, 对Fermat数F_n=2^2^n+1, F_5, F_6都不是素数。那么我们如何分解它们呢？
def factor(num: int) -> list:
资源评论
是空空呀
- 粉丝: 167
- 资源: 3万+
