0

任意の数の因数のモジュールを作成しています。その中には、数 n の素因数分解を見つける 2 つの関数 (一方は他方の呼び出しにつながる) もあります。

発生する問題は、再帰エラーです (再帰の定義が正しい場合)。数値の関数を呼び出すと、すべての素因数が出力され、最後の 2 つの素因数が追加されて再度出力され、これが繰り返し実行されますが、明らかに終わりがありません。

これまでの私のコード:

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)<---これはもともと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 を含む 5 つの言語で実装された、このファクタリング アルゴリズムやその他のアルゴリズムが含まれています。

于 2012-11-21T00:30:55.513 に答える