如何用最简单的python方法求一个数的因子

Question

如何找到一个数的所有因子，并在列表中列出因子。在

输入：

   >>>factors(72)

输出：

^{pr2}$

我已经取下了一些代码，因为这有很多视图，这是一个硬件问题，所以我不想它被复制。在

Answer 1

关于你的问题1：factoring is hard。这就是为什么它是许多密码算法的核心——我们目前还不知道一种快速将一个非常大的数字因子化的方法。在

对于小数字，你的算法就可以了。对于稍微大一点的数字，我已经得到了same question-显然Pollard的Rho是一个很好的算法。对于大量的人，我们不知道。在

现在回答你的问题2：

首先，在您的prime(n)函数中，您不需要一直检查if n%i==0，直到n。您只需要检查到sqrt(n)，因为如果有任何一对整数(a,b)，这样a * b = n，那么这些整数中的一个必然小于或等于sqrt(n)。所以你只需要检查sqrt(n)。这样可以节省大量计算。在

这是您的factors函数：

from math import ceil

def factors(n):
        factors = []
        while n > 1:
                for i in range(2,int((ceil(n/2.0))+1)):
                        if n%i==0:
                                factors.append(i)
                                n = n/i
                                continue
                factors.append(n)
                break
        return factors