对任何给定数字进行质因数分解的程序

Question

n = 600851475143 
i = 2

while i * i < n:
    while n%i == 0:
        n = n / i
    i = i + 1

print (n)

这是 python 中的一个程序，可以找到任何给定数字的最大质因数。我想知道是否有一种方法可以修改它，以便可以找到所有主要因素，而不仅仅是最大的一个。我在想既然这个程序又快又整洁，有没有办法添加几行代码来改变我需要的东西，这是所有主要因素？

Answer 1

这是一个分解整数的简单程序：

Python 2.7.5+ (default, Sep 17 2013, 15:31:50) 
[GCC 4.8.1] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> def factors(n):
...     f, fs = 2, []
...     while f * f <= n:
...         if n % f == 0:
...             fs.append(f)
...             n = n / f
...         else:
...             f = f + 1
...     fs.append(n)
...     return fs
... 
>>> factors(600851475143)
[71, 839, 1471, 6857]

有更好的整数因式分解方法，但这足以让您入门。如果您对使用质数进行编程感兴趣，我谦虚地在我的博客上推荐 this essay。

对任何给定数字进行质因数分解的程序

A program for prime-factorizing any given number

python

prime-factoring