超初心者です。HowTo本"独習C"の内容について

質問

Cを勉強し始めてまだ3日なのですが、
参考書の内容でどうしても理解できない箇所があります。
周りに聞ける人がいないのでここでみなさんにお聞きしてみました。
以下、2つのプログラムでわからない場所があります。

/* 2から1000までの素数を求める */
#include <stdio.h>

int main(void)
{
int i,j,prime;

for(i=2;i<1000;i++){
prime=1;
for(j=2;j<=i/2;j++)
if(!(i%j)) prime=0;
if(prime) printf("%dは素数です\n",i);
}

return 0;
}

iをjで割ったときに余りが0でなければ素数だということはわかるのですが、

for(j=2;j<=i/2;j++)

この行の意味が分かりません。
これはiが2から1000までインクリメントされる間になにをしているのでしょうか？
条件判定部　j<=i/2　はどういった解釈をしたらよいのか分かりません。

あと、本当に基礎的なことなんですがiが2から1000までインクリメントされるのは1回なのですか？
jが2の時にiが1から1000、jが3の時にiが1から1000という意味ではないですよね。
あくまでiが2から1000までインクリメントされるループは1回限りで、その中でjの式が実行されるということですよね。

回答No.1

freedom560 · ベストアンサー

＞for(j=2;j<=i/2;j++)
＞
＞この行の意味が分かりません。
素数を求めたいんですよね？
i=500の時を考えて見ましょう。
j<=250になりますね？ではj=251のときどうなるでしょうか？
500%251を計算します。でも、250より大きい数で割っても当然割り切れることはないですよね？
ここまで説明すればわかりますでしょうか。
つまり、j<=i/2は素数になりうる数だけを取り出そうとしています。

＞iが2から1000までインクリメントされるのは1回なのですか？
iを使ったforループが１回しか出てないからそうですね。

＞jが2の時にiが1から1000、jが3の時にiが1から1000という意味ではないですよね。
そのようにするためには
for(j=2;j<1000;j++)
{
for(i=2;i<=1000;i++){}
}
のようにしなければいけません。

＞あくまでiが2から1000までインクリメントされるループは1回限りで、その中でjの式が実行されるということですよね。
そうです。

お礼

丁重な解説をしていただいてありがとうございます。
最初は回答していただいた内容を呼んでも理解できなかったのですが、ようやく分かりました！

つまりiを2で割った数よりもjが大きい場合は割り切れる数字がないので計算する意味がない、だから最初からj<=i/2以上の値は除外しているというわけですね。

ループの構成についても理解することができました。

これで次に進むことができそうです。
ありがとうございます。

回答No.3

a-saitoh

for(j=2;j<=i/2;j++)
if(!(i%j)){ prime=0;break;}
としたいところですが．．

iが素数でないとしたら，その素因数のうち最小のものは√i　以下です．
そこで，２～int(sqrt(i))までの数でiを割ってどれも割り切れ化ければ素数です．が，浮動小数点演算を避けるために，(無駄ですが)i/2にしているのでしょう．

お礼

回答していただいてありがとうございます。

>２～int(sqrt(i))までの数でiを割ってどれも割り切れなければ素数です
この説明ですべてが理解できました。

本質的にはそのような形で行われる計算なのですね。
int(sqrt(i))の代わりにi/2を使用しているということですね。

また、機会がありましたらよろしくお願いします。

回答No.2

noname#20378

僕はC言語を読める人間ではないのでアルゴリズムに関することだけ
(どーしてもif(!(i%j)) prime=0;
if(prime) printf("%dは素数です\n",i);が中括弧でくくられていないと落ち着かないんだけど、あってるのかなあ...知らないけど^^;;)

>for(j=2;j<=i/2;j++)
なくても動きます。効率が悪いだけで。
iがjで割り切れたら任意の自然数mを用いてi=j*mという形で書けるわけですよね
j>i/2ならm>2ならばj*m>iですから、約数になれません。m=1の時、これを満たすjはiそのものしか存在しませんから、i/2<j<iはiの約数にはなりえないんです。

>あくまでiが2から1000までインクリメントされるループは1回限りで、その中でjの式が実行されるということですよね。

そうです。

お礼

回答していただいてありがとうございます。

数学的解釈が苦手、というかまったくわからないのですが（なのにCをやっている？）理解できました。
精進します^^;

あと、Cの構文的に
for(j=2;j<=i/2;j++)　のターゲットが
if(!(i%j)) prime=0;　のみで、
if(prime) printf("%dは素数です\n",i);　は
for(i=2;i<1000;i++)　のほうのターゲットに含まれているので全体をコードブロック{}で囲む必要はないみたいです（たぶん）。　

またお世話になる時があったらそのときはよろしくお願いします。