素数分解+优化中的递归问题

Question

我正在为任何数字的因子创建一个模块。在它中，我还有两个函数(一个导致调用另一个)，它们找到了数字n的素数分解。

出现的问题是递归错误(如果我对递归的定义是正确的)。当我为一个数字调用函数时，它会打印所有的素数，然后将最后两个素数相加，再次打印，并重复执行，显然没有结果。

到目前为止我的代码：

def primeFactors(n):
from primenum2 import isPrime
from math import sqrt
global pFact, y
x, pFact, y = 2, [], 0
if isPrime(n):
return n
else:
while x <= sqrt(n):
if isPrime(x) and (n%x==0):
pFact.append(x)
y = n / x
if isPrime(y):
pFact.append(y)
print pFact
break
else:
primeFactors2(y)
else:
x += 1
#NEW FUNCTION - I made two functions to avoid another recursion error that was occuring.
def primeFactors2(y):
from primenum2 import isPrime
from math import sqrt
z = 2
while z <= sqrt(y):
if isPrime(z) and (y%z==0):
pFact.append(z)
y = y / z
if isPrime(y):
pFact.append(y)
print pFact
break
else:
primeFactors2(y)
else:
z += 1

当我输入(在外壳中)：primeFactors(600851475143)&lt---这是为Project Euler最初的

预期输出(我已经解决了问题)：[71, 839, 1471, 6857L]

实际输出：

[71, 839, 1471, 6857L]
[71, 839, 1471, 6857L, 1471, 6857L]
[71, 839, 1471, 6857L, 1471, 6857L, 71, 839, 1471, 6857L]
[71, 839, 1471, 6857L, 1471, 6857L, 71, 839, 1471, 6857L, 1471, 6857L]
[71, 839, 1471, 6857L, 1471, 6857L, 71, 839, 1471, 6857L, 1471, 6857L, 71, 839, 1471, 6857L]

它一遍又一遍地这样做，将1471和6857L附加到列表中，然后再次打印。然后，它再次添加所有的素数，然后再次打印。不知道它为什么这么做。任何意见都将不胜感激。此外，如果有任何方法可以让这个代码更快/更Python化，请告诉我：)谢谢

Answer 1

你做的工作太多了。您不需要isPrime或递归函数。以下是基于试除法的整数分解最简单函数的伪代码：

define factors(n)
f := 2
while f * f <= n
if n % f == 0
output f
n := n / f
else
f := f + 1
output n

尽管这对于Project Euler#3来说已经足够了，但还有更好的方法可以对整数进行因子化。当你准备好了，我在我的博客上适度地推荐这篇文章，其中包括这个因子分解算法和其他算法，它们用包括Python在内的五种语言实现。