0

我有一个程序可以找到任意数 n 的质因数。运行它时，我收到一个索引错误，因为索引超出了限制（其中限制是 sqrt(n)）。我不确定为什么它超过了限制。任何人都可以提供任何见解吗？

我的代码适用于大多数数字：

>>> pFactors(250000)
[2, 2, 2, 2, 5, 5, 5, 5, 5, 5]
>>> pFactors(123456789)
[3, 3, 3607, 3803]
>>> pFactors(123456)

Traceback (most recent call last):
  File "<pyshell#2>", line 1, in <module>
    pFactors(123456)
  File "D:\my_stuff\Google Drive\Modules\factors.py", line 50, in pFactors
    check = primes[index]
IndexError: list index out of range
>>> pFactors(123455)

Traceback (most recent call last):
  File "<pyshell#3>", line 1, in <module>
    pFactors(123455)
  File "D:\my_stuff\Google Drive\Modules\factors.py", line 50, in pFactors
    check = primes[index]
IndexError: list index out of range

奇怪的是，到目前为止，我只发现它无法用于数字 123400-1234

这是我的代码：

def pFactors(n):
   import primes as p
   from math import sqrt
   global pFact
   pFact, primes, limit, check, num, index = [], [], int(round(sqrt(n))), 2, n, 0
   if type(n) != int and type(n) != long:
      raise TypeError("Argument <n> can only be <type 'int'> or <type 'long'>")
   else:
      if p.isPrime(n):
         pFact = [1, n]
      else:
         p.prevPrimes(limit)
         for i in p.primes_dict:
            if p.primes_dict[i]:
               primes.append(i)
         while check <= limit:
            if check in primes and (num%check==0):
               pFact.append(check)
               num = num / check
               if num in primes:
                  pFact.append(num)
                  break
            else:
               check = primes[index]
               index += 1
      return pFact

我确信问题不在于primes.py，因为它工作正常。如果有人对如何解决此问题有任何解决方案，请告诉我。谢谢！

4

1 回答 1

2

您想使用平方根的上限作为列表长度，但您只是将其四舍五入，这意味着它有时会向下舍入。

更好的是，使用基于 int 的平方根函数而不是math.sqrt，这样它也适用于对于双精度数来说太大的数字。

此外，global pFact是糟糕的设计。根本没有理由为此使用全局列表，除非您尝试调试它或其他东西，即使那样它也是有问题的。

最后，我不确定为什么要在素数的情况下返回 1 作为一个因素。这违反惯例并且与您的复合案例不一致，但我想如果您真的愿意，您可以这样做。

无论如何，这里有一个简单的方法来做因式分解。一旦你首先让它工作，你就可以担心优化它。

def factor(x):
    n = int(x)
    if n < 1:
        raise ValueError("Argument must be positive")

    factors = []
    d = 2

    while d*d <= n:
        while n%d == 0:
            n = n // d
            factors.append(d)
        d += 1
    if n>1:
        factors.append(n)
    return factors
于 2012-11-26T17:00:58.160 回答