与えられた整数 N より下のすべての素数を見つける最速の方法は何ですか?

N より下のすべての素数をリストする最速の方法

このコード スニペットは、素数のリストを効率的に生成するメソッドの Python 実装を提供します。指定された整数まで。

    def get_primes(n):
        numbers = set(range(2, n + 1))
        primes = []
        while numbers:
            p = numbers.pop()
            primes.append(p)
            numbers.difference_update(set(range(p * p, n + 1, p)))
        return primes

時間複雑さ:

素数の計算にエラトステネスのふるいを使用するため、指定されたコードの時間計算量は O(n log log n) です。

実装ノート:

• このコードは、すべての値を含むセット番号を初期化します。
• まだマークされていない最小の数値のすべての倍数を合成としてマークすることで、数値から素数以外の数値を繰り返し削除します。これらの倍数は、数値を更新するときに現在の素数のストライドを取ることによってスキップされます。
• 数値が空になるとコードは停止し、見つかった素数のリストが素数で返されます。

>潜在的な問題:

開始番号を次のようにマークする実装には潜在的な問題があります。 2 から n までの数値のみを考慮する必要がある場合の素数。これは、ループを 0 ではなく 2 から開始することで修正できます。

使用法:

この実装を使用するには、get_primes 関数を呼び出して、必要な上位値を渡すことができます。引数としてバインドされます。たとえば、1000 までのすべての素数を検索するには、次を使用できます:

primes = get_primes(1000)

出力:

コードの出力は素数のリストになります。指定された整数までの数値。たとえば、n = 1000 でコードを実行すると、次の出力が生成されます:

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ..., 977]

以上が与えられた整数 N より下のすべての素数を見つける最速の方法は何ですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。