4

Python でエラトステネスのふるいを実装しようとしていますが、たとえば779695003923747564589111193840021の平方根までのすべての素数を見つけようとすると、range() の結果に項目が多すぎるというエラーが表示されます。私の質問は、この問題を回避するにはどうすればよいかということです。リストを while ループでインスタンス化すると、(ページファイルの使用を開始する前に) メモリを使いすぎているというエラーが表示されます。2 つを以下に示します。

range() の使用

maxnum = 39312312323123123

primes = []
seq = []
i = 0
seq = range(2,maxnum)

for i in seq:
    mul = i * seq
    for j in mul:
        try:
            seq.remove(j)
        except:
            pass
        primes.append(i)

print primes

while の使用:

maxnum = 39312312323123123

primes = []
seq = []
i = 0
while i < maxnum:
    seq.append(i)
    i+=1

for i in seq:
    mul = i * seq
    for j in mul:
        try:
            seq.remove(j)
        except:
            pass
        primes.append(i)

print primes
4

7 に答える 7

6

「代わりに使用してください」と言いxrange()ますが、実際には、ふるいの結果としてintのリストを使用しています.....したがって、整数ジェネレーターは正しい解決策ではありません。

どの関数を使用しても、39312312323123123 個の要素を含むリストを具体化するのは難しいと思います.... つまり、結局のところ、279 ペタバイトの 64 ビット整数です。

これを試して。

class FoundComposite(Exception): pass

primes = [2]

seq = itertools.takewhile(        # Take integers from a list
          lambda x: x<MAXNUM,     #   until we reach MAXNUM
          itertools.count(2)      #   the list of integers starting from 2
          )

#seq = xrange(2, MAXNUM)          # alternatively

for i in seq:
    try:
        for divisor in primes:
            if not (i % divisor):
                # no remainder - thus an even divisor
                # continue to next i in seq
                raise FoundComposite 
        # if this is reached, we have tried all divisors.
        primes.append(i)
    except FoundComposite:
        pass
于 2010-02-25T21:22:18.487 に答える
2

これはより複雑なアルゴリズムであり、技術的にはふるいとしてカウントされない可能性がありますが、1 つのアプローチは、特定の素数のすべての倍数を一度に削除するのではなく、次の倍数を (素数とともに) キューに入れることです。これは、ジェネレーターの実装で使用できます。キューには依然として多くの (倍数の) 素数が含まれることになりますが、リストを構築してからフィルタリングするほど多くはありません。

原則を示すために、最初のいくつかの手順を手動で行います...

  • 2 は素数 - 収量とキュー (4, 2)
  • 3 は素数 - 収量とキュー (6, 3)
  • 4 は合成です - キュー内の (4, 2) を (6, 2) に置き換えます
  • 5 は素数 - 収量とキュー (10, 5)
  • 6 は合成です - (6, 2) を (8, 2) に、(6, 3) を (9, 3) に置き換えます

注 - キューは FIFO ではありません。最小の最初の項目で常にタプルを抽出しますが、新しい/置換タプルには (通常) 最上位の最初の項目がなく、(上記の 6 と同様に) 重複があります。

Python でキューを効率的に処理するには、タプルの最初の項目をキーとする辞書 (つまり、ハッシュテーブル) をお勧めします。データは、2 番目の項目の値 (元の素数) のセットです。

他の場所で提案されているように、大きなターゲットを試す前に、小さなターゲットでテストしてください。失敗してもあまり驚かないでください。ソリューションを完了するには、一度に (キュー内で) ヒープに割り当てられた大きな整数が多すぎる必要がある場合があります。

于 2010-02-25T21:47:46.613 に答える
2

あなたのアルゴリズムは壊れています。最初に maxnum=100 で動作するようにします。

機能するようになると、 maxnum=100000000 の実行には長い時間がかかることがわかります。

(10,100,1000,10000,100000,1000000...) で maxnum の実行にかかる時間をプロットすると、39312312323123123 にかかる時間を推定できる場合があります:)

于 2010-02-25T21:29:15.583 に答える
1

と呼ばれるPython用のサードパーティモジュールがありますgmpy

非常に高速であるため、便利な機能がいくつかあります。確率論的なものは、約40億のマークを開始します。

next_prime(...)
    next_prime(x): returns the smallest prime number > x.  Note that
    GMP may use a probabilistic definition of 'prime', and also that
    if x<0 GMP considers x 'prime' iff -x is prime; gmpy reflects these
    GMP design choices. x must be an mpz, or else gets coerced to one.

is_prime(...)
    is_prime(x,n=25): returns 2 if x is _certainly_ prime, 1 if x is
    _probably_ prime (probability > 1 - 1/2**n), 0 if x is composite.
    If x<0, GMP considers x 'prime' iff -x is prime; gmpy reflects this
    GMP design choice. x must be an mpz, or else gets coerced to one.
于 2010-02-25T21:41:50.067 に答える
0

これを試して：

def getPrimes(maxnum):
    primes = []
    for i in xrange(2, maxnum):
        is_mul = False
        for j in primes:         # Try dividing by all previous primes
            if i % j == 0:
                is_mul = True    # Once we find a prime that i is divisible by
                break            # short circuit so we don't have to try all of them
        if not is_mul:           # if we try every prime we've seen so far and `i`
            primes.append(i)     # isn't a multiple, so it must be prime
    return primes

非常に多くの素数に到達するまで、メモリが不足しないようにする必要があります。このようにして、倍数のリストを作成することを心配する必要はありません。ただし、これがまだふるいとしてカウントされるかどうかはわかりません。

実際、これはでは機能しませんmaxnum = 39312312323123123。素数定理を使用すると1,028,840,332,567,181、その範囲にほぼ素数があると推定できます。

この質問で指摘されているように、32ビットシステムでのPythonリストの最大サイズはです536,870,912。したがって、メモリが不足していなくても、計算を終了することはできません。

ただし、64ビットシステムではその問題は発生しないはずです。

2 ** 64 => 18446744073709551616

前述の質問の計算を使用する(2 ** 64) / 8と、リスト内の要素の最大数は、2,305,843,009,213,693,951遭遇する素数の推定数よりも多くなります。

編集：

メモリの問題を回避するために、素数のリストをハードディスク上のファイルに保存することができます。1行に1つの素数を格納し、新しい番号を確認するたびにファイルを読み取ります。

多分このようなもの：

primes_path = r'C:\temp\primes.txt'

def genPrimes():
    for line in open(primes_path, 'r'):
        yield int(line.strip())    

def addPrime(prime):
    primes_file = open(primes_path, 'a')
    primes_file.write('%s\n' % prime)
    primes_file.close()

def findPrimes(maxnum):
    for i in xrange(2, maxnum):
        is_mul = False
        for prime in genPrimes():  # generate the primes from a file on disk
            if i % prime == 0:
                is_mul = True    
                break            
        if not is_mul:           
            addPrime(i)  # append the new prime to the end of your primes file

最後に、すべての素数を含むファイルがハードドライブにあります。

さて、これはかなり遅いでしょうが、メモリが不足することはありません。ファイル（ RAIDなど）の読み取り/書き込み速度を上げることで、速度を上げることができます。

于 2010-02-25T21:56:56.107 に答える
0

メモリ制限については、内部的にリストや配列の連結リストであるカスタムリスト（クラス）を作成してみてはいかがでしょうか。.append .remove などの必要性を促進するために必要なメンバーに似た、提供された外部インターフェイスでカスタム リストを呼び出し元が使用するため、内部的に魔法のように一方から他方へトラバースし、必要に応じてさらに追加します。問題で使用される配列。

注: 私は Python プログラマーではありません。私がPythonで言ったことを実装する方法の手がかりではありません。多分私はここで文脈を知らないので、私が反対票を投じられたかどうかはわかります。

Python で呼び出される「ジェネレーター」を使用して、内部リストの結果を 1 つの巨大な単一リストであるかのように生成することもできます。おそらく、リンクされたリストで。

于 2010-02-25T21:40:03.220 に答える
0

range()要求された範囲内のすべての数値を含むリストを返しますが、xrangeはジェネレータであり、ゼロに近いメモリ消費で次々と数値を生成します。

于 2010-02-25T21:27:04.717 に答える