79

明確にするために、これは宿題の問題ではありません:)

私が構築している数学アプリケーションの素数を見つけたかったのですが、Sieve of Eratosthenesアプローチに出会いました。

私はPythonでそれの実装を書きました。しかし、それはひどく遅いです。たとえば、200 万未満の素数をすべて見つけたいとします。20分以上かかります。（私はこの時点でそれを止めました）。どうすればこれをスピードアップできますか?

def primes_sieve(limit):
    limitn = limit+1
    primes = range(2, limitn)

    for i in primes:
        factors = range(i, limitn, i)
        for f in factors[1:]:
            if f in primes:
                primes.remove(f)
    return primes

print primes_sieve(2000)

更新: 私はこのコードのプロファイリングを行ってしまい、リストから要素を削除するのにかなりの時間が費やされていることがわかりました。要素を見つけて削除し、リストを再調整するためにリスト全体（最悪の場合）をトラバースする必要があることを考えると、非常に理解できます（おそらくいくつかのコピーが続きますか？）。とにかく、辞書用のリストを取り出しました。私の新しい実装 -

def primes_sieve1(limit):
    limitn = limit+1
    primes = dict()
    for i in range(2, limitn): primes[i] = True

    for i in primes:
        factors = range(i,limitn, i)
        for f in factors[1:]:
            primes[f] = False
    return [i for i in primes if primes[i]==True]

print primes_sieve1(2000000)
4

21 に答える 21

120

あなたは正しいアルゴリズムを完全に実装していません:

最初の例でprimes_sieveは、（アルゴリズムのように）ストライク/設定解除する素数フラグのリストを維持しませんが、代わりに整数のリストを継続的にサイズ変更します。これは非常に高価です。リストからアイテムを削除するには、後続のすべてのアイテムをシフトする必要があります一つ下。

2 番目の例では、素数フラグのディクショナリprimes_sieve1を維持します。これは正しい方向への一歩ですが、ディクショナリを未定義の順序で反復し、因子の因子を重複して削除します (アルゴリズムのように素数の因子のみではなく)。 ）。キーをソートし、素数以外をスキップすることでこれを修正できますが (これにより、すでに桁違いに高速になります)、リストを直接使用する方がはるかに効率的です。

正しいアルゴリズム (辞書の代わりにリストを使用) は次のようになります。

def primes_sieve2(limit):
    a = [True] * limit                          # Initialize the primality list
    a[0] = a[1] = False

    for (i, isprime) in enumerate(a):
        if isprime:
            yield i
            for n in range(i*i, limit, i):     # Mark factors non-prime
                a[n] = False

i*i(これには、倍数の代わりに素数の正方形 ( ) で非素数のマーキングを開始するアルゴリズムの最適化も含まれることに注意してください。)

于 2010-10-15T11:54:15.150 に答える
15 
def eratosthenes(n):
    multiples = []
    for i in range(2, n+1):
        if i not in multiples:
            print (i)
            for j in range(i*i, n+1, i):
                multiples.append(j)

eratosthenes(100)
于 2014-01-04T18:01:55.047 に答える
8

配列 (リスト) の先頭から削除するには、それ以降のすべての項目を移動する必要があります。つまり、このようにリストからすべての要素を先頭から削除するのは O(n^2) 操作です。

セットを使用すると、これをより効率的に行うことができます。

def primes_sieve(limit):
    limitn = limit+1
    not_prime = set()
    primes = []

    for i in range(2, limitn):
        if i in not_prime:
            continue

        for f in range(i*2, limitn, i):
            not_prime.add(f)

        primes.append(i)

    return primes

print primes_sieve(1000000)

... または、リストを再配置する必要がないようにします。

def primes_sieve(limit):
    limitn = limit+1
    not_prime = [False] * limitn
    primes = []

    for i in range(2, limitn):
        if not_prime[i]:
            continue
        for f in xrange(i*2, limitn, i):
            not_prime[f] = True

        primes.append(i)

    return primes
于 2010-10-15T05:27:01.620 に答える
5

はるかに高速：

import time
def get_primes(n):
  m = n+1
  #numbers = [True for i in range(m)]
  numbers = [True] * m #EDIT: faster
  for i in range(2, int(n**0.5 + 1)):
    if numbers[i]:
      for j in range(i*i, m, i):
        numbers[j] = False
  primes = []
  for i in range(2, m):
    if numbers[i]:
      primes.append(i)
  return primes

start = time.time()
primes = get_primes(10000)
print(time.time() - start)
print(get_primes(100))
于 2015-08-14T14:07:40.060 に答える
2

多くの愛好家 (上記のコメントの Glenn Maynard と MrHIDEn を含む) からの貢献を組み合わせることで、Python 2 で次のコードを思いつきました。

def simpleSieve(sieveSize):
    #creating Sieve.
    sieve = [True] * (sieveSize+1)
    # 0 and 1 are not considered prime.
    sieve[0] = False
    sieve[1] = False
    for i in xrange(2,int(math.sqrt(sieveSize))+1):
        if sieve[i] == False:
            continue
        for pointer in xrange(i**2, sieveSize+1, i):
            sieve[pointer] = False
    # Sieve is left with prime numbers == True
    primes = []
    for i in xrange(sieveSize+1):
        if sieve[i] == True:
            primes.append(i)
    return primes

sieveSize = input()
primes = simpleSieve(sieveSize)

10 乗のさまざまな入力に対する私のマシンでの計算にかかる時間は次のとおりです。

  • 3 : 0.3ms
  • 4 : 2.4ms
  • 5: 23 ミリ秒
  • 6 : 0.26秒
  • 7 : 3.1秒
  • 8:33秒
于 2016-09-04T02:03:53.647 に答える
1

簡単なスピード ハック: 変数「素数」を定義するとき、ステップを 2 に設定してすべての偶数を自動的にスキップし、開始点を 1 に設定します。

次に、 for i in primes の代わりに for i in primes[:round(len(primes) ** 0.5)] を使用してさらに最適化できます。これにより、パフォーマンスが大幅に向上します。さらに、5 で終わる数字を削除して、さらに速度を上げることができます。

于 2015-02-01T21:07:36.220 に答える
1

私はちょうどこれを思いつきました。最速ではないかもしれませんが、単純な加算と比較以外は使用していません。もちろん、ここであなたを止めるのは再帰の制限です。

def nondivsby2():
    j = 1
    while True:
        j += 2
        yield j

def nondivsbyk(k, nondivs):
    j = 0
    for i in nondivs:
        while j < i:
            j += k
        if j > i:
            yield i

def primes():
    nd = nondivsby2()
    while True:
        p = next(nd)
        nd = nondivsbyk(p, nd)
        yield p

def main():
    for p in primes():
        print(p)
于 2020-10-03T16:06:27.187 に答える
0

おそらく、プライマリ番号を取得する最も簡単な方法は次のとおりです。

import sympy
list(sympy.primerange(lower, upper+1))

それらを保存する必要がない場合は、上記のコードを に変換せずに使用してlistください。sympy.primerangeジェネレーターなので、メモリを消費しません。

于 2020-11-28T13:37:51.050 に答える