for文の条件式について

#include<stdio.h>
#define N 30
#define TRUE 1
#define FALSE 0
char is_prime[N+1];
int main(void)
{
for(i=1;i<=N;i++){
is_prime[i]=TRUE;
}
is_prime[1]=FALSE
for(i=2;i*i<=N;i++）→(1)
if(is_prime[i])
for(j=i*2;j<=N;j+=i)→(2)
is_prime[j]=FALSE;→(3)

printf("%dまでの素数は、\n",N);
for(i=1;i<=N;i++)
if(is_prime[i])
printf("%d",i);

return 0;
これはエラトステネスの素数を求めるプログラムですが、(1)のi*iは2 3 5と理解できるんですが（２）の条件式が理解できません。
例えはi=2のときｊは4になるのですが、(3)は　is_prime[4]=FALSEとなりｊ+=iは6になりますが、何ゆえこれが増分として出てくるのか理解できません。
ｊ+=iはどういう使われ方をするのか理解できません。どなたかご教授ねがいます。

No.3 ベストアンサー 回答者： auty 回答日時： 2008/04/08 11:21

・　最初、全ての数を素数に設定して、約平方根までチェックし、

　　素数でないもの除いていきます。

・　それぞれのiについての処理は、その倍数は素数にはなれませんのですべてFALSEに決定します。そのときの、iの倍数を順に求めるのが
　　j+=i
　　です。つまり
　　 for(j=i*2;j<=N;j+=i)
　　で、自分を除くすべてのiの倍数を処理しているわけです。

　　なお、その前の
　　if(is_prime[i])
　　は、既にiにFALSEがあるということは、その倍数についてもFALSEとして処理されている事が保障されていますから、無駄なチェックを省いているわけですね。

この回答へのお礼

for(j*2;j<=N;j+=i)の条件式がiの倍数を処理している事が良く分かり、納得しました。有難うございました。

お礼日時：2008/04/09 05:28

No.4 回答者： masa6272 回答日時： 2008/04/08 16:22

エラトステネスの篩(ふるい)は、一定の数までの素数を効率よく求める方法の1つです。

まず、プログラム云々より、この仕組みを理解してください。

そうすれば、どうしてこんなプログラムになるか分かるはずです。

参考URL：http://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%A9% …

No.2 回答者： xkuonx 回答日時： 2008/04/08 10:20

j+=iはj=j+iと同じ意味です。

また、for文の第一引数(この場合j=i*2)が実行されるのは
for文のループが始まる最初だけです。

No.1 回答者： koko_u_ 回答日時： 2008/04/08 10:18

j には i の倍数が順々に格納されるので、

何かの数の倍数になっていれば素数ではないということだと思います。