5

素因数分解関数を書いたのですが、いじってみると、いくつかの数値に問題があることに気づきました...

>>> 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
4

2 に答える 2

10

次のように変更します。

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]
于 2013-01-27T19:05:24.177 に答える
1

3 で割った後の 999 の例では、結果 (333) も 3 で割ることができ、111 が得られます。これを 3 で割ることもできます (そして 37 を取得します)。しかし、あなたのコードでは、それを一度だけ割ります - あなたがする必要があるのは、現在の数を割り切れる素数を見つけたら、それが不可能になるまでその数で割り続けることです。

于 2013-01-27T18:48:36.077 に答える