c - 数组大小错误

Question

我正在尝试制作一个程序，使用埃拉托斯特尼筛计算不超过整数的素数数量。虽然我的程序对于小数字工作得很好(而且很快)，但在达到一定数字(46337)后，我收到“命令由信号 11 终止”错误，我认为这与数组大小有关。我尝试使用 malloc() 但不太正确。对于大数字(最多 50 亿)我该怎么办？

#include <stdio.h>
#include<stdlib.h>
int main(){
signed long int x,i, j, prime = 0;
scanf("%ld", &x);
int num[x];
for(i=2; i<=x;i++){
  num[i]=1;
}
for(i=2; i<=x;i++){
  if(num[i] == 1){
    for(j=i*i; j<=x; j = j + i){
      num[j] = 0;
    }
    //printf("num[%d]\n", i);
    prime++;
  }
}
 printf("%ld", prime);
 return 0;
}

Answer 1

你的数组

int num[x];

在栈上，只能容纳小数组。对于大数组，您必须分配内存。您可以使用 char 类型来节省内存膨胀，因为您只需要一个状态。

char *num = malloc(x+1);              // allow for indexing by [x]
if(num == NULL) {
    // deal with allocation error
}

//... the sieve code

free(num);

我还建议，您必须使用

检查 i*i 是否违反 int 限制

if(num[i] == 1){
    if (x / i >= i){                  // make sure i*i won't break
        for(j=i*i; j<=x; j = j + i){
            num[j] = 0;
        }    
    }    
}    

最后，您想要达到 50 亿，这超出了 uint32_t(unsigned long int 在我的系统上)42 亿的范围。如果这能让您满意，请将 int 定义更改为 unsigned，注意循环控件不要换行，即使用 unsigned x = UINT_MAX - 1;

如果您没有可用的 5Gb 内存，请按照 @BoPersson 的建议使用位状态。