こんにちはゲストさん。会員登録(無料)して質問・回答してみよう!

解決済みの質問

【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;となるかわかりません。
0と1はどちらも素数ではないと思うので、
私はtrueではないと思うのですが・・・。

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

投稿日時 - 2009-09-24 12:07:20

QNo.5314807

困ってます

質問者が選んだベストアンサー

まず結論から言うとこのプログラムにおいては「そこは使わないのでどちらでも構わない」ということになります.
ただし, このプログラムは腐っています. 動作は正しいですがこのように書いてはいけません. もっと素直に, 例えば
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();
}
}
とでも書くべきです.

投稿日時 - 2009-09-24 13:39:05

お礼

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

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

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

投稿日時 - 2009-09-24 20:11:13

ANo.2

このQ&Aは役に立ちましたか?

0人が「このQ&Aが役に立った」と投票しています

回答(3)

ANo.3

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

投稿日時 - 2009-09-25 00:08:45

お礼

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

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

投稿日時 - 2009-09-26 06:44:18

ANo.1

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

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

投稿日時 - 2009-09-24 12:22:40

お礼

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

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

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

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

投稿日時 - 2009-09-24 20:14:43

あなたにオススメの質問