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 · ベストアンサー

「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;が素数でない処理なのですね。

回答No.4

Oh-Orange

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

お礼

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

回答No.3

morigann

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

回答No.1

php504

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