エラトステネスの篩のJavaプログラムを紹介

2023年3月12日 2023年8月28日山崎講師

山崎講師

エラトステネスの篩とは、指定された範囲内のすべての素数を見つけるための古典的なアルゴリズムの一つです。このアルゴリズムは、紀元前3世紀に古代ギリシャの数学者エラトステネスによって発明されました。

エラトステネスの篩のアルゴリズムを言葉にすると以下のようになります。

素数のリストを作成するためのブール配列を用意する。この配列は、最初はすべて true で初期化されます。
2 から始めて、最初の素数を見つけます。最初の素数は 2 であるため、この素数は配列で true にマークされます。
次に、2 の倍数をすべて false にマークします。これは、2 以外のすべての偶数が合成数であるためです。
次に、まだマークされていない最小の数を見つけます。これが次の素数です。
次の素数のすべての倍数を false にマークします。
4 と 5 を繰り返します。すべての数について処理が終了すると、true にマークされている数は素数です。

このアルゴリズムは、高速かつ効率的であり、現代のコンピュータでも非常に有用です。

講師がエラトステネスの篩を使って10までの素数を見つける手順を以下に板書します。

<プログラム>

<実行結果>

2から100までの素数:
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

<解説>

1.クラス宣言とメソッド定義

public class SieveOfEratosthenes {
public static void findPrimes(int n) {

2.素数を見つけるための配列の初期化

boolean[] isPrime = new boolean[n + 1];
for (int i = 2; i <= n; i++) {
isPrime[i] = true;
}

配列isPrimeを作成し、n + 1個の要素を持つように設定しています。(添字の0を考慮)

配列の各要素は、trueまたはfalseのいずれかに初期化されます。この場合、2からnまでの範囲内で、全ての数は素数である可能性があるため、最初は配列の全要素をtrueに設定します。

3.素数でない数を除外するための篩を実行する

for (int i = 2; i * i <= n; i++) {
if (isPrime[i]) {
for (int j = i * i; j <= n; j += i) {
isPrime[j] = false;
}
}
}

i * i <= nの条件を満たす間、iをインクリメントしながら、isPrime配列を篩い落とします。isPrime[i]がtrueである場合、iの倍数を除外するために、i * iから始めて、iずつインクリメントしながらisPrime[j]をfalseに設定します。

例えば、i = 2の場合、j = 4, 6, 8, 10, 12, ...を除外します。i = 3の場合、j = 9, 12, 15, ...を除外します。i = 4の場合、j = 16, 20, 24, ...を除外します。そして、これを繰り返していくことで、素数でない数を篩い落とします。

i*i <= n という条件は、各素数の倍数を判定する際の上限を決定するために用いられています。

具体的には、i が素数である場合、i の倍数 i*j (j > 1) は既に他の素数の倍数としてマークされているため、再度マークする必要がありません。したがって、i の倍数をマークする際には、i*j が n より小さい範囲に収まっていることを確認する必要があります。

i*j <= n を満たす最大の j を求めるには、j = n / i を用いることができます。しかし、この方法では計算誤差が発生する可能性があるため、代わりに i*i <= n という条件を使って、j の範囲を制限します。

例えば、i = 7, n = 100 の場合を考えてみましょう。j の最大値は j = n / i = 14.28 となりますが、整数で考えると j = 14 が最大値となります。つまり、7*15 = 105 > 100 であり、これ以上 7 の倍数をマークする必要がないことが分かります。したがって、i*i <= n という条件を用いることで、計算量を効率的に削減することができます。

4.素数を表示する

for (int i = 2; i <= n; i++) {
if (isPrime[i]) {
System.out.print(i + " ");
}
}

最後に、篩い落としの結果、isPrime配列の要素がtrueである値を表示するので2からnまでの素数が表示されます。

本記事の内容が、誰かのお役に立ちましたら幸いです。

IT企業向け新人研修おすすめ資料　無料公開中 (saycon.co.jp)

投稿者プロフィール

山崎講師代表取締役

セイ・コンサルティング・グループ株式会社代表取締役。
岐阜県出身。
2000年創業、2004年会社設立。
IT企業向け人材育成研修歴業界歴20年以上。
すべての無駄を省いた費用対効果の高い「筋肉質」な研修を提供します！
この記事に間違い等ありましたらぜひお知らせください。

エラトステネスの篩のJavaプログラムを紹介

投稿者プロフィール

最新の投稿

シーザー暗号のプログラムを紹介

ユークリッドの互除法のJavaプログラムを2種類紹介