0

我正在为任意数量的因子创建一个模块。在其中，我还有两个函数（一个导致调用另一个）来找到数字 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

当我输入（在 Shell 中）时：primeFactors(600851475143)<---这原本是针对 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 附加到列表中，然后再次打印。然后，它再次添​​加所有主要因素，然后再次打印。不知道为什么会这样。非常感谢任何输入。另外，如果有任何方法可以使此代码更快/更 Pythonic，请告诉我 :) 谢谢

4

1 回答 1

2

你做的工作太多了。您不需要 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 在内的五种语言实现。

于 2012-11-21T00:30:55.513 回答