11

私はPythonでコーディングすることを学び始めたばかりです。このプロジェクト オイラーの質問に答えるコードを書き込もうとしています。

13195 の素因数は 5、7、13、29 です。

600851475143 の最大の素因数は?

私のプログラムは 13195 のテスト ケースで動作しますが、600851475143 を入力しようとすると、「OverflowError: range() results has too many items」というエラーが表示されます。

これが私のコードです：

class Euler3:
    "A class to find the largest prime factor of a given number"
     n = 600851475143
     primeFactors = []
     for i in range(2,n):
         if (n%i ==0):
            primeFactors.append(i)
            n = n/i
            i = i -1 #reset i
     print primeFactors

どんな助けや提案も大歓迎です！

4

8 に答える 8

18

このrange関数はリストを作成し、それをメモリに格納しようとします。多数の長いリストを作成すると、OverflowError が発生します。xrange代わりに、オンデマンドで数値を生成するジェネレーターを取得するために使用できます。

そうは言っても、大きな素数を計算するにはアルゴリズムが遅すぎることがわかると思います。素数アルゴリズムはたくさんありますが、出発点としてエラトステネスのふるいをチェックすることをお勧めします。

編集:xrange実際には正しくジェネレーターを返しませんが、ジェネレーターのように動作する xrange オブジェクトを返します。あなたが気にしているかどうかはわかりませんが、私が正確ではないことに悩まされていました!

于 2012-05-28T02:40:45.667 に答える
4

Python 3ではなくPython 2を使用していると思います-range(2,n)実際にリストを作成します! 6000 億個の数値を格納するのに十分なメモリがありません! xrangeでもいいはず。

また、あなたの考えはi=i-1うまくいきません。for ループは C のようには機能せず、そのハックは C スタイルのループでのみ機能します。for ループは を繰り返しrange(2,n)ます。i一度に値を取得する場合は、5何をしても、次回iは取得されます。6

range(2,n)また、ループに入るとリストが作成されます。したがって、n変更しても何も変わりません。

ロジックを少し再考する必要があります。

(信じられない場合は、テスト ケースとして 175 を使用してみてください)

最後のコメントとして、おそらく特殊な整数除算を使用する習慣を身につける必要があります: n = n // i. /Python 2 でも同じように動作しますが、これ//は実際には非推奨の動作であり、Python 3 では同じように動作しません。ここで/は、浮動小数点数が得られます。

于 2012-05-28T02:38:56.990 に答える
4

xrange代わりに使用することで問題を解決できますrange

次の問題は、何らかの条件下でループから抜け出す必要があるため、プログラムの実行に時間がかかりすぎることです。

繰り返し要因に対処するより良い方法は、 を に置き換えることですif。while

     while (n%i ==0):
        primeFactors.append(i)
        n = n/i
于 2012-05-28T02:38:58.207 に答える
2 
n = 600851475143
primeFactors = []
for i in range(2,n):

それに気づくことで機能を最適化できると思います

for i in range(2,n):

あなたは交換することができます

range(2,n)

に

range(2,int(sqrt(n))+2)

なぜなら、あなたはwikiを見ることができるからです...

于 2012-05-28T02:56:17.563 に答える
1

これは、これまでに見つけた素数を見つけるための最良の方法です。

def isprime(n):
    #make sure n is a positive integer
    n = abs(int(n))
    #0 and 1 are not primes
    if n < 2:
        return False
    #2 is the only even prime number
    if n == 2:
        return True
    #all other even numbers are not primes
    if not n & 1:
        return False
    #range starts with 3 and only needs to go up to the square root of n
    #for all odd numbers
    for x in range (3, int(n**0.5)+1, 2):
        if n % x == 0:
            return False
    return True #if it makes it through all the catches, it is a prime
于 2014-01-15T08:49:50.633 に答える