特定の数「n」までの素数を生成するために使用されるエラトステネスのふるいアルゴリズムを試していたところ、インターネットで次のコードに出くわしました。
#include <stdio.h>
#define LIMIT 1500000 /*size of integers array*/
#define PRIMES 100000 /*size of primes array*/
int main(){
int i,j,numbers[LIMIT];
int primes[PRIMES];
/*fill the array with natural numbers*/
for (i=0;i<LIMIT;i++){
numbers[i]=i+2;
}
/*sieve the non-primes*/
for (i=0;i<LIMIT;i++){
if (numbers[i]!=-1){
for (j=2*numbers[i]-2;j<limit;j+=numbers[i])
numbers[j]=-1;
/* An alternate can be: for(j=i+numbers[i]; j<20; j+=arr[i])*/
}
}
/*transfer the primes to their own array*/
j = 0;
for (i=0;i<LIMIT&&j<PRIMES;i++)
if (numbers[i]!=-1)
primes[j++] = numbers[i];
/*print*/
for (i=0;i<PRIMES;i++)
printf("%d\n",primes[i]);
return 0;
}
ふるい部分の内側の for ループを理解できませんでした。GDB を使用してトレースしようとしましたが、出力が何を示しているかを確認するのfor (j=2*numbers[i]-2;j<limit;j+=numbers[i])
が難しくなりました。
誰か親切にできますか:
a) その文を理解するのを手伝ってくれますか? (j=2*数字[i]-2;j
b) GDB がすべてのスタックの内容と実行出力を並行して表示できる方法はありますか? ブレークポイントの使用と使用
print var
は難しそうです。i、numbers[i]、j を 1 つのブレークポイントで、またはより詳細な出力にする必要があるということですか?