素数を求めるプログラム

素数を求める関数の作り方を調べていたら以下のような
プログラムを見つけました。
for文の中は奇数で割り切れるかどうかを調べているということで
いいのでしょうか??何故j*j<=kとなっているのでしょうか??
後、最後のreturn YES;はどのような場合実行されるのでしょうか??

#include<stdio.h>

#define YES 1
#define NO 0

int sosu(int k){
int j;
if(k == 2) return YES;
if(k % 2 == 0) return NO;
for(j=3;j*j<=k;j+=2){
if(k % j == 0) return NO;
}
return YES;
}

No.1 ベストアンサー 回答者： fifaile 回答日時： 2008/05/21 09:42

int sosu(int k){　//実数kが素数かどうかを調べる関数

int j;
if(k == 2) return YES;　//k=2ならば、kは素数である
if(k % 2 == 0) return NO;　//kが偶数ならば、kは素数ではない
for(j=3;j*j<=k;j+=2){　//kが3以上の奇数のとき
if(k % j == 0) return NO;　//k以外の奇数で割り切れれば、素数ではない
}
return YES;　//上記の処理をくぐってくれば素数である
}

です。
y=SQRT(y)^2ですから、SQRT(y)以上の約数が出てくるはずがないんです。
ですから、それ以上の処理はしません。

No.4 回答者： episteme 回答日時： 2008/05/23 06:51

> j*j<=kのところがよくわかりません。

k がいくつかの数の積であらわせるとき、そのうち少なくとも一つは√kより小さくなります。
そうでないと掛け合わせたときkを超えてしまいますから。

なので、kが何かで割り切れるか否かの判定は√kより小さな数について調べれば十分ってことです。

No.3 回答者： culverin 回答日時： 2008/05/21 14:08

j*j<=kについて横から補足すると

j*j<=kという部分はkの平方根とjを比較する代わりにjの二乗とkを比較しているのです。

jとkがともに負でないとき、
j×j≦kであることとj≦√kであることは等価です。

No.2 回答者： mtaka2 回答日時： 2008/05/21 10:21

「素数かどうか」の判定とは、要するに「その数を割ると余りが0になる数が存在しない」ことを確認すればいいわけです。

一つでも割り切れる数があったら、元の数は素数ではない。

で、割り切れるかどうかについては総当たりで調べるわけですが、小さい数から順に調べる場合、

・最初に2で割り切れるかどうか調べておけば、あとは奇数だけしらべれば良い
　偶数で割り切れるような数は2でも割り切れますから「最初の2で割り切れるかどうかチェック」で非素数と判定済になってます。

・最大でも元の数の平方根まで調べればよい
　平方根より大きい数で割り切れる場合、その商(=平方根より小さい)でも割り切れるので、小さい方の数での割り切れるかどうか判定で非素数と判定済となっているはず。
　(例えば、15が素数かどうかチェックするとき、15=3×5ですが
「3で割り切れるかどうか」のチェックをした後なら「5で割り切れるかどうかのチェック」は要らない、ということです)

この回答への補足

皆さん回答ありがとうございます。
だいたい把握することができたのですがやはり
j*j<=kのところがよくわかりません。
引き続きよろしくお願いします。

補足日時：2008/05/21 13:36