【Java】ある数列から、素数を探すプログラムについて

質問

Java初心者です。独学なので質問できる環境が無く、
こちらで質問致します。回答をお願い致します。

以下のプログラムについて質問です。

class Prime {
public static void main(String[] args) {
int max = 100; // 素数を探す数の最大値
boolean[] a = new boolean[max]; // 素数かどうか判定する配列

// 配列の初期化
for(int i = 0; i < max; i++)
a[i] = true;

// 素数かどうか判定
for(int i = 2; i < max; i++) {
if(a[i-1]) {
for(int j = 2; i*j <= max; j++)
a[i * j - 1] = false;
}
else
continue;
}

// 結果を表示
for(int i = 1; i < max; i++) {
if(a[i])
System.out.print((i + 1) + " ");
}
System.out.println();
}
}

上記の「配列の初期化」の個所、
for(int i = 0; i < max; i++)
a[i] = true;
ここでなぜ、a[i] = true;となるかわかりません。
０と１はどちらも素数ではないと思うので、
私はtrueではないと思うのですが・・・。

ぜひとも教えて頂きたいと思います。

回答No.2

Tacosan · ベストアンサー

まず結論から言うとこのプログラムにおいては「そこは使わないのでどちらでも構わない」ということになります.
ただし, このプログラムは腐っています. 動作は正しいですがこのように書いてはいけません. もっと素直に, 例えば
class Prime {
public static void main(String[] args) {
int max = 100; // 素数を探す数の最大値
boolean[] a = new boolean[max+1]; // 素数かどうか判定する配列

// 配列の初期化
for(int i = 2; i <= max; i++)
a[i] = true;

// 素数かどうか判定
for(int i = 2; i <= max; i++) {
if(a[i]) {
for(int j = 2; i*j <= max; j++)
a[i * j] = false;
}
}

// 結果を表示
for(int i = 2; i <= max; i++) {
if(a[i])
System.out.print(i + " ");
}
System.out.println();
}
}
とでも書くべきです.

お礼

回答ありがとうございました！
しかも、新しいプログラムまで書いて下さり、大変うれしいです！

たしかに、
System.out.print(i + " ");
のほうがスッキリしていますね！

本当にありがとうございました！！

回答No.3

Tacosan

一応念の為:
もとのプログラムでもっとも「腐っている」のは, a[i] が「i+1 が素数かどうか」を表しているという点にあります. なぜそこでひねらなければならないのか.
a[i] が「i が素数かどうかを表す」とすれば, #2 で挙げたように素直なプログラムとして書くことができます. デメリットは「配列要素が 1個無駄になる」ですが, たかが 1個のためにこのようにひねる必要はありません. 本当に配列要素を節約したいのなら, もっと違う方法をとるべきです.

お礼

再度コメントありがとうございました！
見やすい・分かりやすいプログラム作りを心がけたいと思います！

本当にありがとうございました！

回答No.1

noname#94983

ここでの処理の考え方は、配列全部にとりあえずtrueを入れておき、その後で繰り返しを使って、ある値の倍数の要素にfalseを入れる、ということをひたすら繰り返している。これで、配列aの中で、何かの数字の倍数（つまりその数字で割り切れる）の要素にはすべてfalseが設定されていく。結果として、trueのまま残っているのは何の数の倍数でもない値（つまり素数）になる、という考え方をしている。

だから、最初の繰り返しでa[i] = true;するのは、「とりあえず全部にtrueを入れておく」ということであって、０や１が素数だろうがそうでなかろうが関係ない。初期化というのはそういうことなのだから。とりあえず全部入れておき、それからその後で１つ１つについて調べていく、ということなんだから。

お礼

とても早い回答、ありがとうございます！！

＞配列全部にとりあえずtrueを入れておき、その後で繰り返しを使って、ある値の倍数の要素にfalseを入れる

なるほど、そのような意味だったのですね。もう一度「初期化」の確認を致します。

改めてありがとうございました！