5

エラトステネスのふるいkは、次のように限界まで素数を生成する適度に高速な方法です。

  1. p = (2, 3, 4, ..., k)セットとから始めi = 2ます。
  2. から始めて、からのi^2すべての倍数を削除します。ip
  3. iの次に小さいものについてp、まで繰り返しi >= sqrt(k)ます。

私の現在の実装は次のようになります（すべての偶数を事前にフィルタリングするという明らかな最適化を使用）：

# Compute all prime numbers less than k using the Sieve of Eratosthenes
def sieve(k):
    s = set(range(3, k, 2))
    s.add(2)

    for i in range(3, int(sqrt(k)), 2):
        if i in s:
            for j in range(i ** 2, k, i * 2):
                s.discard(j)

    return sorted(s)

編集：これは同等のlistベースのコードです：

def sieve_list(k):
    s = [True] * k
    s[0] = s[1] = False
    for i in range(4, k, 2):
        s[i] = False

    for i in range(3, int(sqrt(k)) + 2, 2):
        if s[i]:            
            for j in range(i ** 2, k, i * 2):
                s[j] = False

    return [2] + [ i for i in range(3, k, 2) if s[i] ]

これは機能しますが、完全には正しくありません。台詞：

for i in range(3, int(sqrt(k)), 2):
    if i in s:
        [...]

s奇数ごとにセットメンバーシップをテストして、の次に小さい要素を見つけます。理想的には、実装は実際には次のようになります。

while i < sqrt(k):
    [...]
    i = next smallest element in s

ただし、setは順序付けされていないため、次に小さい要素をより効率的に取得する方法がわかりません（または可能であっても）。list素数にwith True/フラグを使用することを検討しましたFalseが、それでも次の要素listを探して歩く必要があります。Trueどちらかから実際に要素を削除することはできませんlist。これにより、手順2で合成数を効率的に削除できなくなります。

次に小さい要素をより効率的に見つける方法はありますか？そうでない場合、O(1)値による削除と次に小さい要素を見つける効率的な方法を可能にする他のデータ構造はありますか？

4

2 に答える 2

7

セットは、ハッシュセットとして内部的に実装されているため、順序付けされていません。このようなデータ構造で最小要素を見つける効率的な方法はありません。min(s)これを行うための最もPython的な方法です（ただし、O（n）です）。

collections.deque セットと一緒に使用できます。を使用しdequeて、要素のリストをソートされた順序で保存します。最小値を取得する必要があるたびdequeに、セット内にある要素が見つかるまで要素をポップします。これにより、入力配列全体でO（1）コストが償却されました（n回ポップするだけでよいため）。

また、リストからのO（n）の作成（またはO（1）の挿入）、値によるO（1）の削除、およびO（1）の最小値の検索を行うデータ構造はあり得ないことも指摘しておく必要があります。このようなデータ構造を使用して、O（n）の一般的な並べ替えを簡単に実装できます。これは（情報理論的には）不可能です。ハッシュセットはかなり近くなりますが、効率的な最小検出を犠牲にする必要があります。

于 2012-09-16T16:19:21.420 に答える
0

セットの代わりにリストを使用できます。マークされていない場合は、Noneでリストを初期化します。要素インデックスを数値として使用できます。

  1. リストを初期化する
  2. p=2から開始します
  3. リスト内のすべての倍数pを「M」でマークします
  4. リスト内の次のマークされていない要素を見つけて、それを新しいものにしpます。ない場合は、完了です。

次のマークされていないインデックスを見つける必要がある場合は、インデックスの後にpあり、Noneに等しい要素を簡単に調べることができます。

于 2012-09-16T16:01:49.213 に答える