Python - 整数分解为质数

Question

我写了一个整数分解的函数，但在玩弄它的时候，我发现它对某些数字有问题...

>>> pFactors(99) # it does work for numbers with multiple of one prime factor
[3, 3, 11]
>>> pFactors(999) # however, sometimes, it doesn't
[3, 37] # the actual prime factorization of 999 is [3, 3, 3, 37]. 
>>> pFactors(88)
[2, 11]
>>> pFactors(888)
[2, 3, 37]

我的代码哪里出错了？

def pFactors(n):
   """Finds the prime factors of 'n'"""
   from primes import isPrime
   from math import sqrt
   pFact, limit, check, num = [], int(round(sqrt(n), 2)) + 1, 2, n
   if isPrime(n):
      return [n]
   for check in range(2, limit):
      if isPrime(check) and num % check == 0:
         pFact.append(check)
         num /= check
         if isPrime(num):
            pFact.append(num)
            break
   pFact = sorted(pFact)
   return pFact

Answer 1

在999这个例子中，当你把它除以3时，结果是333，而333也可以被3整除，这样你又得到了111，111也可以继续除以3（得到37）。但是在你的代码里，你只除了一次。你需要做的是，一旦找到一个能整除当前数字的质数，就要一直用这个质数去除，直到不能再除为止。

Answer 2

这样修改：

def pFactors(n): 
        """Finds the prime factors of 'n'""" 
        from math import sqrt 
        pFact, limit, check, num = [], int(sqrt(n)) + 1, 2, n 
        if n == 1: return [1] 
        for check in range(2, limit): 
             while num % check == 0: 
                pFact.append(check) 
                num /= check 
        if num > 1: 
          pFact.append(num) 
        return pFact 

for i in range(1,1000):
        print pFactors(i)

虽然我喜欢你最初写的代码，但有几点需要注意：

1. 你不需要用到isPrime这个函数。原因是，在限制范围内，任何能整除num的质数，都会是能整除num的合数的最小因子。所以，当你把这些质数除掉后，就不会再找到它们组成的合数作为因子了，这样你只会剩下质因子。

2. 你不需要对数组进行排序，因为它已经因为check是按顺序递增的而自然排序了。

3. 添加的这个while循环可以确保只要因子继续整除num，就能正确找到重复的因子。

4. 你可以用同余来过滤掉限制范围内大约2/3的数字，这样就能减少检查的因子，你能看出来怎么做吗？

上面结果的最后几行是：

[11, 89]
[2, 2, 5, 7, 7]
[3, 3, 109]
[2, 491]
[983]
[2, 2, 2, 3, 41]
[5, 197]
[2, 17, 29]
[3, 7, 47]
[2, 2, 13, 19]
[23, 43]
[2, 3, 3, 5, 11]
[991]
[2, 2, 2, 2, 2, 31]
[3, 331]
[2, 7, 71]
[5, 199]
[2, 2, 3, 83]
[997]
[2, 499]
[3, 3, 3, 37]