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

・　最初、全ての数を素数に設定して、約平方根までチェックし、
　　素数でないもの除いていきます。

・　それぞれの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の倍数を処理している事が良く分かり、納得しました。有難うございました。

回答No.4

masa6272

エラトステネスの篩(ふるい)は、一定の数までの素数を効率よく求める方法の1つです。まず、プログラム云々より、この仕組みを理解してください。

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

参考URL：

http://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86%E3%83%8D%E3%82%B9%E3%81%AE%E7%AF%A9

回答No.2

xkuonx

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

回答No.1

koko_u_

j には i の倍数が順々に格納されるので、
何かの数の倍数になっていれば素数ではないということだと思います。