素数プログラムの解読、

C言語のプログラムで素数を求めるプログラムで、

//入力された数字が素数がどうかを求めるプログラムです。

#include<stdio.h>

main()
{
int a,c; //aはそれが素数かどうか調べたい数字です。

printf("aに何か好きな整数をいれてください。\n");
printf("a=");
scanf("%d",&a);
c = 2;

while ( a%c ){
c += c%2+1;
printf("途中計算 %d\n",c);
}
if ( a > 1 && c == a ){
printf("素数です。\n");
}else{
printf("素数ちゃうよ。\n");
}
}

というのを作りました。このプログラムは
教えてgooの回答欄にあったものを自分で
いじったものですが、

c = 2;

while ( a%c ){
c += c%2+1;
printf("途中計算 %d\n",c);
}
の部分が何をしているのかが、わかりません。
printf("途中計算 %d\n",c);　は
何をしているかが解るかもしれないと思い
自分で付足しましたが、やっぱりわかりません。
だれか解る方お願いします。

No.1 ベストアンサー 回答者： arukamun 回答日時： 2003/08/22 10:32

こんにちは、arukamunです。

これって、私が書いたコードですね。

c = 2; //ｃの初期値を2にしています。
while ( a%c ){ // a÷cの余りが0でないならループします。
・・
c += c%2+1; // cにc%2+1を加えます。
printf("途中計算 %d\n",c); // cを表示しています。
} // ループ終了

cは2,3,5,7,9,11,13,15,17,・・・と変化している様子がわかると思います。
c = 2;
while ( a%c ){
c += c%2+1;
13まで素数ですので、かなり無駄が少ないですね。
仮に
c = 2;
while ( a%c ){
c ++ ;
であった場合、cは2,3,4,5,6,7,8,9,10,11,12,13,14,15,・・・・と無駄な計算を沢山行いますね。
aが素数であるの判定は、
aより小さい数で割りきれなければ素数です。
けれどもこれらをすべて計算する必要は無いです。
aより小さい素数で割り切れなければ素数です。
で良いわけです。
その為の枝狩りが
c += c%2+1;
ですね。

この回答へのお礼

ありがとうございます！
大変わかりやすいです。
c += c%2+1;
の考え方がいいですね！

お礼日時：2003/08/25 21:06

No.3 回答者： V-bravo-U 回答日時： 2003/08/23 01:17

　Ｃ言語では「０は偽判定／０以外は全て真判定」という暗黙の約束があります。

　質問者はこれがわからなかったのではないでしょうか？
　この定義から次のように書くこともよくあります。
if(a % c)
{
/* (a % c != 0)の時にここが実行される */
}
else
{
/* (a % c == 0)の時にここが実行される */
}

　ですから、「while ( a%c )」というところは「while (a % c != 0)」と
書き換えることができます。意味は全く同じです。よって「a÷cの余りがあるなら
ループ／なくなった時点でループを抜ける」ということになります。

　話が前後しますが、「c = 2」とあるのは素数の定義により「１以外の自然数で
割りきれる数が１と与えられた自然数のみ」という定義に基づいて２が与えられて
いるものです。

　あとはご存知かと思いますがループ内の「c += c % 2 + 1」は右側の計算が先に
行われて左側に結果を格納します。よって、最終結果が変数c に入るというわけです。

この回答へのお礼

ありがとうございます。
＜暗黙の約束
それはわかったいたのですが、その下が
計算部分がわかりませんでした、

お礼日時：2003/08/25 20:13

No.2 回答者： ranx 回答日時： 2003/08/22 10:33

cを2で割った余りに1を加えた数をcに加えます。

つまりcが偶数なら1を、cが奇数なら2を加えます。
2,3,5,7,9,・・・
という数列を生成しているわけですね。
素数でないものも含まれてしまいますが、
簡便な方法を採ったのでしょう。

この回答へのお礼

ありがとうございます、
わかりやすいです。

お礼日時：2003/08/25 21:07