与えられた範囲内のすべての素数を効率的に見つけるにはどうすればよいでしょうか?

指定された範囲内で素数を見つける: 最適化されたアプローチ

この記事では、指定された範囲内のすべての素数を効率的に識別するという課題に取り組みます。 素数とは、定義上、1 とそれ自体以外に正の約数を持たない 1 より大きい自然数です。

欠陥のあるアプローチとその修正

この問題を解決しようとする最初の試みには、ロジックに重大な欠陥が含まれていました。コードは 0 から反復され、潜在的な素数として 0 と 1 が誤って含まれており、誤った素数テストが使用されていました。条件 if (i != j && i % j == 0) は素数ではなく合成数を識別します。 正しいアプローチには、数値が 1 とそれ自体以外の数値で割り切れないかどうかをチェックすることが含まれます。

試験分割ふるいを使用した最適化されたソリューション

はるかに効率的な方法は、試験分割ふるいを利用することです。 このアプローチでは、いくつかの主要な最適化を利用します。

1. 平方根の制限: ターゲット数値の平方根までの割り算のみをテストする必要があります。数値の約数が平方根より大きい場合は、約数も平方根より小さくなければなりません。

2. 倍数の削除: 素数が特定されると、その倍数が候補リストから削除され、その後のチェックの数が大幅に削減されます。

3. 反復推定: コードは、近似式 (π(x)

最適化されたコード (簡潔にするために LINQ を使用) は、次の戦略を効果的に実装します。

Enumerable.Range(0, Math.Floor(2.52*Math.Sqrt(num)/Math.Log(num))).Aggregate(
    Enumerable.Range(2, num-1).ToList(), 
    (result, index) => { 
        var bp = result[index]; var sqr = bp * bp;
        result.RemoveAll(i => i >= sqr && i % bp == 0); 
        return result; 
    }
);

この洗練されたアルゴリズムにより、特に広範囲を扱う場合、単純なアプローチと比較してパフォーマンスが大幅に向上します。

、Enumerable.Range、ToList、RemoveAll を使用すると、コンパクトで効率的な実装が可能になります。Aggregate

以上が与えられた範囲内のすべての素数を効率的に見つけるにはどうすればよいでしょうか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。