0

特定の数「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 つのブレークポイントで、またはより詳細な出力にする必要があるということですか?

4

1 に答える 1

1 
for (i=0;i<LIMIT;i++){
    numbers[i]=i+2;
}

番号nはスロットn - 2(の場合n >= 2) に入ります。

for (j=2*numbers[i]-2;j<limit;j+=numbers[i])

numbers[i]だったn = i+2ので2*numbers[i] - 2 = 2*(i+2) - 2、のスロットも覚えておいてください2*n。

     numbers[j]=-1;

nから始まるのすべての倍数について、2*nその数を複合としてマークします。(これは貧弱なふるいであり、メモリを使いすぎており、クロスオフする作業が多すぎます。)

Examining the stack

backtrace
where
Show call stack.
backtrace full
where full
Show call stack, also print the local va-
riables in each frame.
frame <frame#>
Select the stack frame to operate on.

gdb のスタックを調べるのに役立つかもしれません。

于 2013-05-27T11:29:34.650 に答える