エラトステネスのふるいアルゴリズム: Python, C++ 例

エラトステネスの篩は最も単純な素数篩です。これは、指定された制限内のすべての素数を検索する素数アルゴリズムです。素数篩にはいくつかあります。たとえば、エラトステネスの篩、アトキンの篩、スンダラムの篩などです。

言葉 "ふるい」とは物質をろ過する器具を意味します。したがって、次のふるいアルゴリズムは、 Python 他の言語では、素数を除外するアルゴリズムを指します。

このアルゴリズムは、反復的なアプローチで素数をフィルタリングします。フィルタリングプロセスは、最小の素数から始まります。素数とは、1 より大きく、約数が 1 とその数自体の XNUMX つしかない自然数のことです。素数ではない数は合成数と呼ばれます。

エラトステネス法のふるいでは、最初に小さな素数が選択され、その倍数がすべて除外されます。プロセスは、指定された範囲内のループで実行されます。

例：

2 から 10 までの範囲の数値を考えてみましょう。

エラトステネスの篩を適用すると、素数2、3、5、7のリストが生成されます。

エラトステネスのアルゴリズムふるい

エラトステネスのふるいのアルゴリズムは次のとおりです。

ステップ1） 2 から指定された範囲 n までの数字のリストを作成します。最小かつ最初の素数である 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=2 を選択したので、25 から 25 までの数字のリストを取得します。

ステップ2） 次に、リスト内の最小の数値 x を選択します。最小の素数であるため、最初は 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 までの素数になります。

疑似コード

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++ コード例

#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 プログラム例

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)

出力：

分割ふるい

エラトステネスのふるいは、数値範囲全体にわたってループを実行する必要があることがわかりました。したがって、数値を格納するために 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)))

次に、次について学びます。パスカルの三角形

まとめ

エラトステネスの篩は、与えられた上限内の素数を除外します。
素数のフィルタリングは、最小の素数「2」から始まります。これは繰り返し行われます。
反復は n の平方根まで行われます。ここで、n は指定された数値範囲です。
これらの反復の後、残った数字が素数になります。

よろしければ：