质因子分解 Python

质因子分解 Python

质因子分解 P y t h o n Python Python
要做质因子分解，首先需要明白什么是质数，以及如何快速判断质数。

质数
质数，也称素数，是只能被1和其本身整除的数，规定1不是质数。

质数的判断可以详见我另一篇博客 判断质数 Python Java C++

def isPrime(n: int) -> bool:
if n <= 3:
return n >= 2
if (n + 1) % 6 != 0 and (n – 1) % 6 != 0:
return False
for i in range(2, int(n ** 0.5) + 1):
if n % i == 0:
return False
return True

质因子分解
质因子分解，故名思意，将一个数分解成所有因子都是质数。

首先判断待分解这个数本身是不是质数，如果他本身就是一个质数的话，那他的质因子就是他自己，因为1不是质数。

如果不是质数，就从2开始，往上一个个质数除。如果可以整除这个质数，那么这个质数就是其一个因子。保存这个质数到一个列表中，再将待分解的数整除这个质数，继续分解即可。

质数列表，可以用列表生成式[i for i in range(2, 10) if isPrime(i)]生成一个质数列表，这个刚开始生成几个就够了，如果数量不够的话，再补充。如果刚开始数量就大的话，复杂度会比较大，大部分数不需要这么大，真用到了，后边再补充就行

if i >= len(primes) – 1:
primes += [i for i in range(i + 1, i + 1000) if isPrime(i)]

完整代码
# 判断是否是质数
def isPrime(n: int) -> bool:
if n <= 3:
return n >= 2
if (n + 1) % 6 != 0 and (n – 1) % 6 != 0:
return False
for i in range(2, int(n ** 0.5) + 1):
if n % i == 0:
return False
return True

# 质因子分解
def factor(n: int) -> list[int]:
ans = []
if isPrime(n): # 判断本身是否是质数
ans.append(n)
return ans
primes = [i for i in range(2, 10) if isPrime(i)] # 生成待循环整除的质数列表
i = 0 # 初始化下标
while not isPrime(n):
if n % primes[i] == 0: # 判断待分解的数是否可以整除这个质数，若能，则这个质数是其一个因子
ans.append(primes[i]) # 保存质因子到列表中
n //= primes[i] # 待分解数整除该质数
i = 0 # 重置质数列表下标(重新从2,3,5…开始判断整除)
else:
i += 1 # 如果不能整除，则下标后移，判断下一个质数是否能整除
if i >= len(primes) – 1: # 如果质数列表的长度不够，就扩充一部分，如果遇到数组超限，就加大1000这个判断区间值
primes += [i for i in range(i + 1, i + 1000) if isPrime(i)]
ans.append(n) # 保存n，由于while循环判断，此时n是*后一个质数
return ans

print(factor(2021041820210418)) #输入待分解的数，即可输出质因子列表