1. 概要

素数は常に興味深いトピックです。 しかし、それらを生成するためのクリーンで有限の式を見つけることができた人は誰もいません。 したがって、数学者はそれを行うためにアルゴリズムと計算能力に依存してきました。 これらのアルゴリズムの中には時間がかかるものもあれば、より高速なものもあります。

このチュートリアルでは、いくつかのよく知られたアルゴリズムを調べて素数を見つけます。 最も古いものから始めて、最新のもので終わります。

素数を見つけるためのほとんどのアルゴリズムは、素数ふるいと呼ばれる方法を使用します。 素数の生成は、特定の数が素数であるかどうかを判断することとは異なります。 そのために、フェルマーの素数性テストミラー-ラビン法などの素数性テストを使用できます。 ここでは、素数を検索または列挙するアルゴリズムのみに焦点を当てます。

2. エラトステネスのふるい

エラトステネスのふるいは、与えられた数までの素数を見つけるための最も古くて簡単な方法の1つです。これは、素数のすべての倍数を合成としてマークすることに基づいています。 そのためには、最初の素数として始まり、そのすべての倍数()をマークします。 次に、マークされていない次の数値()を素数としてマークし、そのすべての倍数()を取り消します。 までの他のすべての番号についても同じことを行います:

ただし、ご覧のとおり、いくつかの数値は数回交差しています。 それを回避するために、各素数について、その倍数をマークすることから始めることができます。 その理由は、プロセスで素数に達すると、その倍数はすべて、すでに消されているよりも小さいためです。 たとえば、に到達するとします。 次に、それを確認でき、すでにとでマークされています。 結果として、から始めることができます。

アルゴリズムは、次のように擬似コードの形式で記述できます。

このアルゴリズムの複雑さを計算するには、外側のループと内側のループを考慮する必要があります。 前者の複雑さは簡単にわかります。 ただし、後者は少し注意が必要です。 が素数のときにループに入るので、現在の素数を使用して、内部演算を何度も繰り返します。 その結果、次のようになります。

   

彼らの本(数論)では、HardyWrightがそれを示しています。 したがって、エラトステネスのふるいの時間複雑さはになります。

3. サンダラムのふるい

この方法は、エラトステネスのふるいと同じ合成数を消す操作に従います。 ただし、それは別の式で行います。 が与えられ、未満の場合、最初に、未満の形式のすべての数値を取り消します。 その後、残りの数を2倍にして、を追加します。 これにより、すべての素数が。未満になります。 ただし、偶数の素数()だけが生成されるわけではありません。

このアルゴリズムの擬似コードは次のとおりです。

入力としての場合、出力はまでの素数であることに注意してください。 したがって、最初に入力を半分に分割して、素数を最大にします。

このアルゴリズムの複雑さは、時間の経過とともに実行される外側のループと、時間よりも短い時間で実行される内側のループを考慮することで計算できます。 したがって、次のようになります。

   

これは、エラトステネスのふるいの複雑さによく似ています。 ただし、エラトステネスのふるいの値と比較して、取ることができる値には違いがあります。 素数のみを取ることができますが、との間のすべての数を取ることができます。 その結果、合計額が大きくなります。 この調和級数直接比較テストを使用すると、次のように結論付けることができます。

   

結果として、このアルゴリズムの時間計算量はになります。

4. アトキンのふるい

アトキンのふるいは、素数を生成するプロセスを(漸近的に)高速化します。 ただし、他のものよりも複雑です。

まず、アルゴリズムは、を除いて60より小さい素数のsieveを作成します。 次に、ふるいを別々のサブセットに分割します。 その後、各サブセットを使用して、特定の2次方程式の解であり、その特定のサブセットと同じモジュロ60の剰余を持つ数値をマークします。 結局、それは平方数の倍数を排除し、残りのものと一緒に戻ります。 結果は、よりも小さい素数のセットです。

アトキンのふるいのプロセスを擬似コードを使用して表現できます。

アトキンのふるいの最初の3つのループには操作が必要であることが簡単にわかります。 最後のループも時間内に実行されると結論付けるには、ループを終了する条件に注意を払う必要があります。 平方数の倍数であるandが、より大きい場合、ループから抜け出し、両方とも時間内に実行されます。 結果として、このアルゴリズムの漸近実行時間はです。

この実行時間を以前の実行時間と比較すると、アトキンのふるいが素数を生成するための最速のアルゴリズムであることがわかります。ただし、前述したように、より複雑な実装が必要です。 さらに、その複雑さのために、入力数が少ない場合、これは最速のアルゴリズムではないかもしれませんが、漸近的な実行時間を考慮すると、他のアルゴリズムよりも高速です。

5. 結論

この記事では、与えられた数までの素数を生成するために使用できるいくつかの高速アルゴリズムを確認しました。