Python で単純な素数ジェネレーターを最適化するにはどうすればよいですか?

Python での単純な素数ジェネレーターの最適化

提供されている Python コードは素数を生成することを目的としていますが、効率を高めるために改善が必要です。

元のコードの問題:

1. ループは割り算をチェックしますが、除数が見つかった場合でもカウントを誤って出力します。
2. Continue ステートメント現在の反復を終了しますが、除数が見つかったときに検索を完全に停止するには、break に置き換える必要があります。

改善されたコード:

import math

def main():
    count = 3
    while True:
        isprime = True
        for x in range(2, math.ceil(math.sqrt(count)) + 1):
            if count % x == 0: 
                isprime = False
                break
        if isprime:
            print(count)
        count += 1

説明:

• 外側のループは、次に考えられる素数をテストするためにカウントをインクリメントします。
• 内側のループは、カウントの平方根まで実行されます。平方根より大きい除数には、平方根よりも小さい除数が対応します。
• カウントが任意の x で割り切れる場合、isprime フラグが False に設定され、内部ループが中断されます。
• 約数が見つからない場合、カウントは素数として出力されます。

高度な素数生成:

より効率的な素数生成の場合、エラトステネスのふるいが推奨されます。以下はコメント付きの最適化された Python 実装です:

def gen_primes():
    D = {}
    q = 2
    while True:
        if q not in D:
            yield q
            for later in range(q * q, 1000000, q):
                D[later] = [q]
        else:
            for later in range(q + D[q][0], 1000000, q):
                D.setdefault(later, []).append(q)
            del D[q]
        q += 1

以上がPython で単純な素数ジェネレーターを最適化するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。