for文＆if文を使った問題について教えてください。

参考書の練習問題を解いていて、応用力がないのか理解できない
ので、分かる方教えていただけませんか？

問題：
キーボードから整数を入力させ、その数が素数であるかどうかを
判断するコードを記述してください。

解答：
import java.io.*;
class SampleP5
{
public static void main(String[] args) throws IOException
{
System.out.println("2以上の整数を入力してください。");
BufferedReader br =
new BufferedReader(new InputStreamReader(System.in));

String str = br.readLine();
int num = Integer.parseInt(str);

for(int i=2; i<=num; i++){
if(i =　= num){
System.out.println(num + "は素数です。");
}
else if(num % i =　= 0){
System.out.println(num + "は素数ではありません。");
break;
}
}
}
}

例えば"7"を入力すると「7は素数です」と出力されるようなんですが、
『i = 7』だとして、『 if(i =　= num)』の条件って当てはまるん
ですか？for文でiの初期値が2だから、『2 =　= 7』で当てはまらない
と思うんですが・・・
考え方が間違っているんですかね？
※ちなみに(= =)のところ、実際はスペース空いてません。
　ここの画面での表示上くっついて1本の線になってしまうので、
　スペースを空けて入力したまでです。

No.3 ベストアンサー 回答者： luckymako 回答日時： 2008/03/22 01:29

素数の定義はいろいろあるかと思いますが

「1と自分自身以外の数で割り切れない数」
と習ったことがあるのではないでしょうか？

このプログラムはこの定義そのものです。

1 で 割り切れるのは当たり前なので 2 から自分自身(num)まで
( for(int i=2; i<=num; i++){} )全ての数で割ってみて
あまり(num % i)が 0 ならば素数ではないのでそこで終了。
最後まで行き着いた(i == num)ならばそれは素数だということです。

最初のifは最後の最後まで真になりません。逆に次のifの方が重要で
こちらが真になれば素数でないと断定できるということです。

補足ですが、残念なことにこの回答を書いた方は無駄なことをしています。
まずfor文の終了条件がにi<=numと書かれているので最初のifは冗長です。
また、num / 2 まで繰り返せば十分です。

この回答へのお礼

回答ありがとうございました。
おかげ様で理解できました。

最後の
＞補足ですが、残念なことにこの回答を書いた方は無駄なことをしてい　ます。
　まずfor文の終了条件がにi<=numと書かれているので最初のifは冗長　です。
　また、num / 2 まで繰り返せば十分です。
のところだけ、ちょっとよく分からなかったですが・・・

応用力がないので、ちょっと言葉の言い回しが変わるだけで？？？ってなってしまって。難しいです・・・

お礼日時：2008/03/22 03:40

No.5 回答者： luckymako 回答日時： 2008/03/22 10:54

すみません間違いました。

最初のif文
if(num / 2 <= i) を
if(num / 2 < i) に修正してください。

No.4 回答者： luckymako 回答日時： 2008/03/22 10:51

まずifが冗長というところですが、

for文の繰り返し条件で
i <= num (1) を、
最初のif文で
i == num (2) を、
判定しています。
(2)の条件は(1)に含まれていますよね？
また、
(1)は i が num 以下の間、繰り返しなさいと読めますが、
これを i が num と異なる間、繰り返しなさいと考えることもできます。これを条件式にすると
i != num　→　!(i == num)
となり同じ条件式の否定というところまで持っていくことが出来ます。
ここまでくると 2 回条件を判断するのはもったいない気がしてきます。

つぎに num / 2 についてですが
num が num より小さい数で割りきれるとき、その正の正数を i とすると、
i = num ではないので、ある正の正数 j との積として
i * j = num (1 < i < num, 1 < j < num, 1 < num) (3)
という式が成り立たなくてはいけません。
このとき、i がとりうる最大を考えると、j が 最小の素数 2 であるとき i が最大になることがわかります。
j = 2 を式(3)に当てはめ、i について解くと
i * 2 = num
i = num / 2
となり、i が最悪一番大きくなったとしても
num / 2 より大きくなることはないことがわかります。
よって、i を 2 から num / 2 まで動かすだけで十分であると言え、
計算回数、比較回数を半減させることが出来ます。

二つを適用してみました。入力は省略↓

public static void main(String[] args) {
　int num = 13;
　int i = 2;
　while(true){
　　if(num / 2 <= i){
　　　System.out.println(num + "は素数です。");
　　　break;
　　}
　　if(num % i == 0){
　　　System.out.println(num + "は素数ではありません。");
　　　break;
　　}
　　i++;
　}
}

No.2 回答者： auty 回答日時： 2008/03/21 23:24

この場合、for文は

iが2から7まで1ずつ増えながら、ぐるぐる回って
{
if (i == num) {
System.out.println(num + "は素数です。");
} else if (num % i == 0) {
System.out.println(num + "は素数ではありません。");
break;
}
}
の部分を6回繰り返します。
iが２のときは、言われるとおり『2 == 7』で当てはまらない（falseを返す）ので
{
System.out.println(num + "は素数です。");
}
は実行されず、
else if (num % i == 0) {
System.out.println(num + "は素数ではありません。");
break;
}
の部分が実行されます。
iが3から6までも同じです。
iが7になって初めて、『7 == 7』が成立し（trueを返す）、
{
System.out.println(num + "は素数です。");
}
の部分が実行されます。
この結果、７が１とそれ自身以外の数で割り切れないことが分かり、「素数です」と表示しているわけです。

この回答への補足

＞else if (num % i == 0) {
　System.out.println(num + "は素数ではありません。");
　break;
　}
　の部分が実行されます。

でもこの場合iが2のときは、(num % i == 0)も当てはまらないと思うのですが・・・
つまり、どちらの文も当てはまらないから、どちらも実行されないんじゃないかと・・・

＞iが7になって初めて、『7 == 7』が成立し（trueを返す）、
　System.out.println(num + "は素数です。");
　の部分が実行されます。

この部分はよく理解できました。
ただ、7を入力すると『7は素数です。』と1文だけ出力される
ということは、『7 == 7』が成立するまではなにも実行されずに
ループが行われるということでしょうか？

理解力がなくてすみません！

補足日時：2008/03/21 23:51

No.1 回答者： koko_u_ 回答日時： 2008/03/21 23:17

まずはテストしてみましょう。

7は素数と判定できたのですね。8はどうですか？9は？

この回答への補足

さっそくの回答ありがとうございます！

＞まずはテストしてみましょう。
　7は素数と判定できたのですね。8はどうですか？9は？

8⇒「8は素数ではありません。」
9⇒「9は素数ではありません。」と出力されました。
8の場合・・・
iの初期値が2なので、
else if(num % i == 0)
↑この時trueになる為、「8は素数ではありません。」と
いう結果になるのは理解できますが、9となるとやっぱり
if文・else if文ともにfalseのような気がして・・・

数学も苦手だから、余計理解できないんでしょうね。

補足日時：2008/03/21 23:19