c - 为什么我的筛子收到 SIGSEGV

Question

好吧，只是为了好玩，我正在研究埃拉托色尼筛。 它最初运行良好，因此我寻求提高其运行时复杂性。现在，我不知道为什么，但我遇到了段错误。 代码如下:

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    int* check = malloc(1000000000 * sizeof(int));
    long long int i;
    for(i = 0;i < 1000000000;i++)
    {
        check[i] = 0;
    }
    int j = 0;
    for(i = 2;i <= 1000000002;i++)
    {
         if(check[i] == 0)
         {
            printf("%lld\n", i);
            for(j = 1;j < (1000000001/i);j++)
            {
                check[j*i] == 1;
            }
         }
    }
return 0;   
}

任何有关失败原因的帮助将不胜感激。

Answer 1

您的代码有多个错误，其中任何一个都可以解释段错误。首先，您没有检查 malloc 的返回值，它可能是 NULL，即使您完全确定它不可能是这样。

其次，当您将 i 从 2 迭代到 1000000002 时，您超出了分配的数组的边界。有这么多零，很难观察，所以这里是带有分隔符的数字:

Initial allocation: 1,000,000,000
Range of i: 2 to 1,000,000,002 inclusive

在循环结束时，您将访问超出数组末尾的内存。