使用python分解质因数

每个合数都可以写成几个质数相乘的形式，其中每个质数都是这个合数的因数，把一个合数用质因数相乘的形式表示出来，叫做分解质因数，也叫做分解质因子。

使用python进行质因数分解可以利用Sympy库

Sympy库的下载安装

如果未下载Sympy库，可以在终端中输入

1
pip install sympy

factorint函数分解质因数

1
2
3
4
5
6
7
from sympy import factorint

k = 366131711084116972797754155655428661136606301399405028536784695081831603930386464285107163569536400

#对k进行质因数分解
factors = factorint(k)
print("对k质因数分解的结果为",factors)

输出的结果为：

1
对k质因数分解的结果为 {2: 4, 3: 2, 5: 2, 7: 8, 13: 2, 31: 2, 43: 2, 109: 2, 239: 2, 691: 2, 8521: 2, mpz(1697946359): 2, 29429628701749048733: 2}

观察到输出若干 a:b的结构，该结构代表k的质因数中有b个a

即k = 2⁴ * 3² * 5² * 7⁸ * 13² * …… * 29429628701749048733²

分解结果转化为列表

很多时候我们还需要对分解得到的质因数进行其他操作，可能需要将字典转化为列表

可以通过如下操作

1
2
factor_list = [p for p, exp in factors.items() for _ in range(exp)]#列表推导式，表示将字典p：exp中的p重复exp次
print("展开后的质因数列表为:", factor_list)

把这两行加在原代码后面，得到结果

1
展开后的质因数列表为: [2, 2, 2, 2, 3, 3, 5, 5, 7, 7, 7, 7, 7, 7, 7, 7, 13, 13, 31, 31, 43, 43, 109, 109, 239, 239, 691, 691, 8521, 8521, mpz(1697946359), mpz(1697946359), 29429628701749048733, 29429628701749048733]

注：出现mpz类型是因为sympy在处理大整数时使用了多精度库，mpz类型比int更加精确，出现mpz一般不会影响我们操作。