日本語
日本語
素数は、それ自体でのみ分割できる自然数を指します。素数を見つけることは、プログラミングの一般的な問題の1つです。この記事では、古典的で効率的なプライムナンバーソリューション方法 - エラトステネスのふるいを紹介します。このアルゴリズムは、素数とその倍数をマークすることにより、指定された範囲のすべての素数を迅速に見つけます。
Elatoseniフィルタリング方法は、長年のシンプルで効果的なアルゴリズムであり、そのコアアイデアは次のとおりです。
Trueの初期値を使用して、長さN+1のブールアレイを作成します。
2から、各プライム番号のマーク倍数が偽として。
Trueの最終的な残りの値を持つ要素は素数です。
次のサンプルコードは、PHPを使用してこのフィルタリング方法を実装する方法を示しています。
function sieveOfEratosthenes($n) {
// の長さを作成します n+1 ブールアレイ，初期値はです true
$isPrime = array_fill(2, $n - 1, true);
// から2始める，各素数の倍数をマークします false
for ($i = 2; $i * $i <= $n; $i++) {
if ($isPrime[$i]) {
for ($j = $i * $i; $j <= $n; $j += $i) {
$isPrime[$j] = false;
}
}
}
// すべてを集めます true の数，つまり、素数です
$primes = [];
foreach ($isPrime as $number => $is) {
if ($is) {
$primes[] = $number;
}
}
return $primes;
}
$range = 100;
$primes = sieveOfEratosthenes($range);
// 出力プライム番号
foreach ($primes as $prime) {
echo $prime . " ";
}
コードは最初にサイズn+1のブールアレイを作成し、最初にそれを真に設定し、次にプライムナンバーの倍数を1つずつ誤ったものとして1つずつマークします。最後に、Trueとマークされたすべてのインデックスが収集されます。つまり、プライムナンバーセットです。
上記のコードを実行し、100の範囲で素数の出力は次のとおりです。
<span class="fun">2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97</span>
この方法は、特定の範囲ですべての素数を正確かつ効率的に見つけることができることがわかります。
Elatoseniフィルタリング法の時間の複雑さは、小範囲から中範囲の素数の迅速なスクリーニングに適したO（n log log n）についてです。暴力的な判断と比較して、スクリーニングが大幅に改善されるたびに、より多くの非優先順位が除外されます。
この記事では、PHPによって実装されたElatoseniフィルタリング方法を紹介します。これは、シンプルで効率的なプライムナンバースクリーニングアルゴリズムです。このアルゴリズムを習得すると、素数を含むプログラミングの問題を解決し、コードの効率とパフォーマンスを改善するのに役立ちます。
