C言語＜素数を求めるプログラム＞

#include<stdio.h>
int j;
int prime(int n)
{
int i;

if(n < 2) return 0;
if(n == 2) return 1;
if(n%2 == 0) return 0;

for(i = 3; i*i<= n; i += 2){
if(n%i == 0) return 0;
}
return 1;
}

int main(void)
{
int n;

for(n=1; n <= 1000; n++)
{
if(prime(n)){

printf("%d\n",n);
j++;
}
}
printf("素数の個数は全部で %d 件見つかりました。\n",j);

return 0;
}

このプログラムは1から1000までの素数のみを表示させるプログラムでありますが、このアルゴリズムが全くわかりません。
int prime(int n)の中身のアルゴリズムがどういう仕組みになっているのかお分かりになりますでしょうか？

No.2 ベストアンサー 回答者： morigann 回答日時： 2007/06/21 13:50

「int prime(int n)」内についてですが、

if(n < 2) return 0;
　→２未満の数字は素数としない、つまり「１」の時は素数ではないと判断したい処理ですね
if(n == 2) return 1;
　→２の時は無条件に素数と判断する為です
if(n%2 == 0) return 0;
　→ｎを２で割った時のあまりが０だったら素数ではない、つまり（２より大きい）偶数の時は絶対素数ではないので偶数をはぶく為の処理ですね
for(i = 3; i*i<= n; i += 2){
if(n%i == 0) return 0;
}
　→割る数（ｉ）を３から５、７、９・・・のように増やしていって、ｎを割ったときのあまりが０かどうか判断しています。
　　例：ｎ＝９場合、ｉ＝３の時に９／３であまりが０になるので、９は３で割り切れるから９は素数じゃない！
　　の処理をしています。
return 1;
　→で、最後のreturnですが、これは説明不要でしょか？
　　ここに来るまで素数じゃないと判断されたらreturn 0で途中で処理を抜けています。
　　つまりここまで来たら素数なのでreturn 1を返します。

で、よろしいでしょうか？

この回答へのお礼

大変わかりやすい回答有難うございました。
こちらと致しましても、なんかわかりそうな気がしました。

return 1;が素数の処理で、return 0;が素数でない処理なのですね。

お礼日時：2007/06/21 14:19

No.4 回答者： Oh-Orange 回答日時： 2007/06/21 15:04

★アドバイス

・morigann さんへ。
＞初期値不定のまま、いきなり「ｊ＋＋」してしまうと計算結果が無茶苦茶になる可能性あります。
　↑
　j はグローバル変数なので初期化されますよ。つまり 0 です。
・gigab3476 さんへ。
　なぜ、j 変数はグローバル変数にしているのですか？
　特に他の関数などで参照しないのであれば j は main() 関数内で宣言(初期化)しておきましょう。
　int main( void )
　{
　　int j = 0;　←初期化
　　int n;
　　　：
　　printf( "素数の個数は全部で %d 件見つかりました。\n", j );
　　return 0;
　}
・以上。

この回答へのお礼

なるほど。そうなんですか。
丁寧なご指摘有難うございます。

お礼日時：2007/06/21 15:54

No.3 回答者： morigann 回答日時： 2007/06/21 13:55

余談ですが＃２の追記です。

ｊが初期化されてないので、int main(void)のＦｏｒ文に入る前に０で初期化しておくべきです。
初期値不定のまま、いきなり「ｊ＋＋」してしまうと計算結果が無茶苦茶になる可能性あります。

No.1 回答者： php504 回答日時： 2007/06/21 13:35

試し割りの素数判定法ですね

nが素数かどうかを判定するのに3から√nまでの整数で順番に試しに割ってみて割り切れたら素数ではないという方法です。