我对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 质量有问题吗？我在笔记本电脑上运行该程序。
您的问题绝对不是小到864的数字的复杂性。相反，当您执行此操作时：
while functools.reduce(operator.mul, factorlist, 1) != a:
for x in range (1, a):
...
你所做的基本上是每次不减少时遍历所有可能的素数。这是多余的，因为您只需要浏览一次列表。
对于像 2000 这样的输入，你进入一个无限循环，因为它永远不会减少到 2000 - 这就是它一直运行的原因。您可以在 while 和 for 之间添加打印因子列表，以准确查看正在发生的事情。
如果只是删除 while 语句，则可以更快地获得结果。
（请注意，我同意费迪南德·拜尔（Ferdinand Beyer）对上述大数的评论。我只是说，在您的特定情况下，864 不是一个很大的数字，并且您的程序中存在错误。
代码的问题在于，你在调用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)
它的运行速度比你的代码快得多。
这是一个最快的;
n = 600851475143
i = 2
while i * i < n:
while n%i == 0:
n /= i
print (i)
i += 1
您可以在此处找到此方法的说明。n 是数，i 是素因数。
