素因式分解python

Question

我对python非常陌生，我想我会创建一个程序，返回给定数字的素因子。这是我的密码：

import math
import operator
import functools

def isprime (n):
    if n == 1:
        return False
    elif n == 2:
        return True
    else:
        for x in range (2, int(math.sqrt(n))+1):
            if n % x == 0:
                return False
                break
        else:
            return True



def factors (a):
    factorlist = []
    if isprime(a) == True:
        print "The number is a prime."
    else:   
        while functools.reduce(operator.mul, factorlist, 1) != a:
            for x in range (1, a):
                if a % x == 0:
                    if isprime(x) == True:
                        factorlist.append(x)
        factorlist.sort()
        print factorlist

testnumber = int(input("Enter a number."))
factors(testnumber)

我的问题是，取决于数字，它需要很长的时间。它可以立即解决100或1000，但2000或864只是不工作！我让它以864作为我的输入，运行了45分钟，但它没有打印任何东西。是不是和我的CPU质量有关？我在笔记本电脑上运行程序。

Answer 1

代码的问题是在调用functools.reduce(operator.mul, factorlist, 1)中重复执行一些昂贵的计算，并且重复检查isprime(x)中是否有相同的数字(而isprime本身由于循环而代价高昂)。

为了避免functools.reduce调用，您只需对已知的因素进行分解，就像@howaboutNO的解决方案中那样，对所考虑的数字进行变异，或者进行递归调用(参见下面)。

为了避免使用相同值调用isprime(x)的开销，可以使用回忆录，这是工具集中的一个方便的技巧。

应用这两种方法，我得出了以下结论：

import math

def memoize(f):
    memo = {}
    def helper(x):
        if x not in memo:
            memo[x] = f(x)
        return memo[x]
    return helper

@memoize
def isprime (n):
    if n == 1:
        return False
    elif n == 2:
        return True
    else:
        for x in range (2, int(math.sqrt(n))+1):
            if n % x == 0:
                return False
                break
        else:
            return True


def factors (a):
    if a == 1:
        return []
    elif isprime(a):
        return [a]
    else:
        for x in range (2, int(math.sqrt(a))+1):
            if a % x == 0:
                return [x] + factors(a/x)

testnumber = int(input("Enter a number."))
print factors(testnumber)

运行速度比代码快得多。

Answer 2

你的问题肯定不是864这样小的数字的复杂性。相反，当你这样做时：

while functools.reduce(operator.mul, factorlist, 1) != a:
    for x in range (1, a):
        ...

你所做的实际上是每一次都不减少所有可能的质数。这是多余的，因为无论如何您只需要浏览一次列表。

对于像2000这样的输入，您将进入一个无限循环，因为它永远不会减少到2000 --这就是为什么它一直在运行。您可以将print factorlist添加到while和for之间，以查看所发生的确切情况。

如果您只是删除while语句，您将能够更快地获得结果。

(请注意，我同意Ferdinand关于上述大量数字的评论。我只是想说，在你的具体情况下，864并不是一个很大的数字，而且你的程序中也有一个bug。)

Answer 3

这里是最快的；

n = 600851475143 
i = 2

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

您可以在这里中找到对此方法的解释。n是数和i的素因子。