0

我正在尝试Eratosthenes 的 Sieve算法，该算法用于生成直到给定数字“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 在一个断点或更详细的输出？

4

1 回答 1

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

数字n进入插槽n - 2（for n >= 2）。

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

请记住，numbers[i]was 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 回答