エラトステネスアルゴリズムのふるいの時間計算量

1. 概要

このチュートリアルでは、エラトステネスのふるいアルゴリズムについて説明します。アルゴリズムの時間計算量分析も示します。

数が与えられた場合、入力整数までのすべての素数を見つける必要があります。

Sieve of Eratosthenesアルゴリズムは単純ですが、セグメント内でそれらを見つける最も効率的な方法の1つです。 アルゴリズムの最初のステップは、から入力番号までのすべての番号を書き留めることです。

より大きい任意の入力数の場合、最初の素数は常に。になります。したがって、から指定された入力整数までの連続する整数のリストを作成します。この時点で、最初の素数が見つかりました。 次に、の倍数であるすべての整数をリストから削除します（これは最初の素数であるため）。

次の素数を選択し続け、現在の素数が以下になるまで、リストから現在の素数の倍数を削除します。最後に、リストに残るすべての整数は素数です。

Sieve of Eratosthenesアルゴリズムの手順について説明しました。ここで、擬似コードを見てみましょう。

ここでは、数値を入力として受け取り、サイズの配列を作成します。配列のインデックスは数値を表し、配列内の値はそれが素数であるかどうかを示します。内部の値が、の場合、その合成数。同様に、内部の値が、の場合、それは素数です。

これは素数ではないことがわかっているので、に初期化し、残りのインデックスをに初期化することからアルゴリズムを開始します。各反復で、ループ値を設定し、それが複合数であるか素数であるかを確認します。素数の場合は、その素数の倍数であるすべての整数をリストから削除します。

現在のループ値が。以下になるまでアルゴリズムを実行します。最後に、値が。であるすべてのインデックスを返します。

取りましょう。最初のステップは、サイズのリストを作成し、最初のインデックスをに割り当て、残りを次のように割り当てることです。

次に、反復を開始します。最初に、ループ値をに設定し、配列のインデックスに値が含まれているかどうかを確認します。のインデックスにが含まれている場合、現在のループ値の倍数であるすべてのインデックスに割り当てます。

次に、ループの値をに設定し、同じプロセスを続行します。

次のループ値はですが、ご覧のとおり、その値はです。したがって、次のインデックスに移動して、同じプロセスを繰り返します。

次の素数はですが、アルゴリズムによれば、現在の素数が。以下になると停止します。これが、したがってです。したがって、次の素数を続行せず、アルゴリズムを終了します。アルゴリズムは値を持つインデックスを返します。これらはすべて素数です。

このアルゴリズムの中核となる部分は、合成数をマークし、を割り当ててリストから削除することです。ここで、合成数をマークしてそれに値を割り当てるには時間がかかります。このアルゴリズムの実際の複雑さは、合成数をマークするためにループが実行される回数にあります。

合成数を削除するために、の現在の素数の倍数に値を割り当てます。ここで、現在の素数がであると仮定しましょう。最初の反復では、要素にマークを付けます。このように、現在の素数がである場合、合成数に割り当てます。ループを実行する合計回数は次のようになります。

この方程式を解いてみましょう。

素数の合計の調和数列を使用すると、次のことが証明できます。

したがって、エラトステネスのふるいアルゴリズムの合計時間計算量はになります。

このチュートリアルでは、エラトステネスのふるいアルゴリズムについて詳しく説明しました。アルゴリズムの擬似コードを提示し、時間計算量を分析しました。