エラトステネスの篩 Python & C++
サラ・チェン
エラトステネスの篩とは何ですか？
エラトステネスの篩は、最も単純な素数篩です。これは、与えられた範囲内のすべての素数を見つけるために使用される素数アルゴリズムです。エラトステネスの篩、アトキンの篩、スンダラムの篩など、いくつかの素数篩が存在します。
言葉 "ふるい」は物質を濾過する器具を指します。同様に、ふるいアルゴリズムは Python また、他の言語では、整数のリストから素数を除外する方法を指します。
このアルゴリズムは、反復的なアプローチを用いて素数をフィルタリングします。フィルタリング処理は、最小の素数から始まります。素数とは、1より大きい自然数で、約数が1とその数自身のみである数のことです。 Numbers 素数ではない数は合成数と呼ばれます。
エラトステネスの篩を使う理由とは？
エラトステネスの篩法では、まず小さな素数を選び、その倍数をすべて除外します。このプロセスは指定された範囲でループ実行され、各候補に対して試行除算を行うことなく、nまでのすべての素数を効率的に生成します。
これにより、素数判定を1つずつ行うよりも、篩法の方が高速になります。この方法は、多数の素数を迅速に生成する必要がある数論、暗号理論、ハッシュ関数、競技プログラミングなどの分野で広く用いられています。
具体的な例を挙げますと、以下の通りです。
2から10までの数字の範囲を考えてみましょう。
エラトステネスの篩を適用すると、素数のリストである2、3、5、7が得られます。
エラトステネスのアルゴリズムふるい
エラトステネスのふるいのアルゴリズムは次のとおりです。
ステップ1） 2から指定された範囲nまでの数値のリストを作成します。2は最小の素数であり、最初の素数であるため、2から始めます。
ステップ2） リストの中で最小の数 x (初期値は x = 2) を選択し、リストを走査して、選択した数の倍数をすべてマークすることで、対応する合成数をフィルタリングします。
ステップ3） 次に、リスト上の次の素数またはマークされていない最小の数字を選択し、ステップ 2 を繰り返します。
ステップ4） x の値が n の平方根以下になるまで前の手順を繰り返します (x<=
).
注意： 数学的な推論は非常に単純です。数の範囲nは次のように因数分解できます。
n = a * b
繰り返しますが、n = *
= (より小さい係数 ) * (より大きい係数 )
したがって、少なくとも XNUMX つは、 素因数 または両方が <= である必要があります したがって、 十分になります。
ステップ5） これら4つのステップの後、マークされていない残りの数字は、指定された範囲n内のすべての素数になります。
実例
例：
具体例を挙げて、その仕組みを見ていきましょう。
この例では、2から25までの素数のリストを見つけます。したがって、n = 25となります。
ステップ1） 最初のステップでは、n = 25 を選択したので、2 から 25 までの数字のリストを取得します。
ステップ2） 次に、リストの中で最小の数 x を選択します。最初は、最小の素数である 2 を選択します。次に、リストを順に見ていき、2 の倍数に印を付けます。
与えられたnの値に対する2の倍数は、4、6、8、10、12、14、16、18、20、22、24です。
注意： 青色は選択された数字を、ピンク色は除外された倍数を表します。
ステップ3） 次に、マークされていない次に小さい数値である 3 を選択し、3 の倍数にマークを付けて最後のステップを繰り返します。
ステップ4） x = になるまでステップ 3 を同じように繰り返します 
または5。
ステップ5） 残りのマークされていない数字は、2から25までの素数です。
擬似-Code
以下の擬似コードは、エラトステネスの篩の基本的な構造を捉えたものであり、これを実際のコードに変換する前の段階を示しています。
Begin
Declare a boolean array of size n and initialize it to true
For all numbers i : from 2 to sqrt(n)
IF bool value of i is true THEN
i is prime
For all multiples of i (i<n)
mark multiples of i as composite
Print all unmarked numbers
End
エラトステネスの篩 C/C++ Code 例:
以下は完全なものです C++ エラトステネスの篩の実装で、指定された上限までのすべての素数を出力する。
#include <iostream>
#include <cstring>
using namespace std;
void Sieve_Of_Eratosthenes(int n)
{
// Create and initialize a boolean array
bool primeNumber[n + 1];
memset(primeNumber, true, sizeof(primeNumber));
for (int j = 2; j * j <= n; j++) {
if (primeNumber[j] == true) {
// Update all multiples of i as false
for (int k = j * j; k <= n; k += j)
primeNumber[k] = false;
}
}
for (int i = 2; i <= n; i++)
if (primeNumber[i])
cout << i << " ";
}
int main()
{
int n = 25;
Sieve_Of_Eratosthenes(n);
return 0;
}
出力：
2 3 5 7 11 13 17 19 23
エラトステネスのふるい Python プログラム例
以下 Python このプログラムは、ブールリストとwhileループを使用して同じアルゴリズムを実装します。
def SieveOfEratosthenes(n): # Create a boolean array primeNumber = [True for i in range(n+2)] i = 2 while (i * i <= n): if (primeNumber[i] == True): # Update all multiples of i as false for j in range(i * i, n+1, i): primeNumber[j] = False i += 1 for i in range(2, n): if primeNumber[i]: print(i) n = 25 SieveOfEratosthenes(n)
出力：
2 3 5 7 11 13 17 19 23
分割ふるい
エラトステネスの篩は、数の範囲全体をループ処理することがわかります。そのため、数を格納するには O(n) のメモリ領域が必要です。n が大きいほど大きなメモリブロックを割り当てることは現実的ではないため、非常に大きな範囲で素数を見つけようとすると状況は複雑になります。
このアルゴリズムは、いくつかの新しい機能を導入することで最適化できます。アイデアは、数値範囲を小さなセグメントに分割し、それらのセグメント内の素数を1つずつ計算することです。これは、空間計算量を削減する効率的な方法です。この方法は、 分割されたふるい。
最適化は次の方法で実現できます。
- 簡単なふるいを使って2から
そしてそれらを配列に格納します。 - 範囲 [0…n-1] を最大で複数のサイズのセグメントに分割します .
- 各セグメントについて、セグメントを反復処理し、ステップ 1 で見つかった素数の倍数をマークします。このステップには O(）最大で。
通常のふるいには O(n) の補助メモリ スペースが必要ですが、セグメント化されたふるいには O(これは、nが大きい場合には大幅な改善となる。ただし、この方法には時間計算量を改善しないという欠点もある。
複雑さの分析
空間計算量と時間計算量の両方を理解することで、与えられた問題規模に対して、通常の篩法と分割篩法のどちらを選択すべきかを判断するのに役立ちます。
スペースの複雑さ：
単純なエラトステネスの篩アルゴリズムは O(n) のメモリ空間を必要とします。セグメント化された篩は O() 補助スペース。
時間計算量：
通常のエラトステネスの篩アルゴリズムの時間計算量はO(n*log(log(n)))です。この計算量の理由については、以下で説明します。
与えられた数 n に対して、合成数（つまり素数でない数）をマークするのに必要な時間は一定です。したがって、ループの実行回数は次のようになります。
n/2 + n/3 + n/5 + n/7 + ……∞
= n * (1/2 + 1/3 + 1/5 + 1/7 +…….∞)
素数の和の調和数列は、log(log(n))として導出できる。
(1/2 + 1/3 + 1/5 + 1/7 +…….∞) = log(log(n))
したがって、時間計算量は次のようになります。
T(n) = n * (1/2 + 1/3 + 1/5 + 1/7 + ……∞)
= n * log(log(n))
したがって、時間計算量はO(n * log(log(n)))となります。
次に、あなたは パスカルの三角形.
