我在这个网站上看到了很多用Python进行整数因数分解的方法，但是并不真正理解它们，所以我尝试用自己的方法来实现：
def factorisation(n):
fact = []
i = 2
while i<=n:
if n%i==0:
fact.append(i)
n//= i
else:
i+=1
return fact
我认为它是有效的，但我不太清楚为什么while循环从i到n...从我的课程中，我学到了我们必须从2到sqrt(n)进行判断。
我是否有什么误解？
我能否改进它？
谢谢 :)
你可以使用Pollard's rho整数分解算法。与其他速度较慢的算法相比，它效率很高且快速。例如：
from math import gcd
def factorization(n):
factors = []
def get_factor(n):
x_fixed = 2
cycle_size = 2
x = 2
factor = 1
while factor == 1:
for count in range(cycle_size):
if factor > 1: break
x = (x * x + 1) % n
factor = gcd(x - x_fixed, n)
cycle_size *= 2
x_fixed = x
return factor
while n > 1:
next = get_factor(n)
factors.append(next)
n //= next
return factors
对于小数字，它非常快速，在这种情况下仅花费了0.035秒。
print(factorization(823767))
~$ time python3 factorization.py
[3, 7, 39227]
real 0m0,035s
user 0m0,031s
sys 0m0,004s
print(factorization(41612032092))
~$ time python3 factorization.py
[3, 4, 37, 1681, 127, 439]
real 0m0,038s
user 0m0,034s
sys 0m0,004s
如果我们使用非常大的数字，会花费更多时间，但考虑到这是一个巨大的数字，这仍然是一个非常合理的时间。在这种情况下，只需要 28.128 秒。
print(factorization(23756965471926357236576238546))
~$ time python3 factorization.py
[3, 3, 2, 479, 11423, 582677, 413975744296733]
real 0m28,128s
user 0m28,120s
sys 0m0,008s
希望这能对你有所帮助。祝好。
factorization(144) 返回的是 [3, 3, 8, 2] 而不是我需要的 [3, 3, 2, 2, 2, 2]。不完整的因数分解只在2上吗？还是不可预测的？ - uhohn不能被小于sqrt(n)的任何数字整除时，那就足以说明n是质数。在这种情况下，你将不会发现除n本身外的任何其他因子。sqrt(n)处停止循环，并将n的剩余值添加到质数因子列表中。fact.append(n)。 - interjay这个带有驱动程序的函数
def factors(n):
global tmp
answ=[]
tmp=(n)
addends=[4,2,4,2,4,6,2,6]
def divn(dvr):
global tmp
while tmp%(dvr)==0:
answ.append(dvr)
tmp=tmp//dvr
divn(2)
divn(3)
divn(5)
d=(7)
while (d)*(d)<=tmp:
for i in range(8):
divn(d)
d=d+(addends[i])
if tmp>1:
answ.append(tmp)
return answ
print(factors(23756965471926357236576238546))
在4秒内找到了
[2, 3, 3, 479, 11423, 582677, 413975744296733]
它通过在测试这三个质数后跳过2、3和5的倍数来实现。在测试完这三个数之后，它只需要测试每30个数字中的8个，从7开始，按照给定的加数列表中的加数循环添加到先前测试过的数字上。这样可以减少用作测试的非质数的数量。（30是235，因此这构成了这些数的倍数的循环）。
每个尝试的数字都会尝试多次，直到剩余的数字不再能被它整除。
它使用一个函数内部的函数来进行实际的除法尝试。
def factoring(x, print_eq=True):
factors = []
if x == 2:
factors += [x]
for i in range(2,x):
if i*i > x:
factors += [x]
break
if x%i == 0:
factors += [i]
factors += factoring(x//i, False)
break
# Factorization has been completed.
# Print the result in pretty mode
if print_eq:
if x in factors:
print(f'{x} = 1 * {x} is a prime')
else:
eq = ''
nf = {i : factors.count(i) for i in factors}
fs = list(sorted(nf))
for i, f in enumerate(fs):
if nf[f] > 1:
eq += f'{f}^{nf[f]}'
else:
eq += f'{f}'
if i < len(fs) - 1:
eq += ' * '
print(f'{x} = {eq}\n')
return factors
如果你只是想找到最小的因子（比如在素数测试中），那么你只需要去到floor(sqrt(n))层。如果你想要所有的因子，那么你应该从0到n/2进行检查。
简而言之：
素性测试：
n = int(input('Please input a number: ')
sn = int(sqrt(n))
for x in range(2,sn+1):
if n%x == 0:
print('Not prime. Divisible by: '+str(x))
print(str(n)+' is prime')
分解：
n = int(input('Please input a number: ')
n2 = int(n/2)
fn = []
for x in range(2,n2+1):
if n%x == 0:
fn.append(x) #lower member of factor pair
fn.append(n/x) #upper member of factor pair
print('N has the following factors: '+str(fn))
希望这能帮助你理解。