数组大小错误

Question

我正在尝试制作一个程序，使用 Eratosthenes 筛法计算不超过整数的素数数量。虽然我的程序对于小数字运行良好（并且快速），但在一定数字 (46337) 之后我得到一个 "command terminated by signal 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 的建议使用位状态。

Answer 2

以下代码检查错误，使用最大 5000000000 的值进行测试，正确输出素数的最终计数，使用 malloc 以避免溢出可用堆栈 space。

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

int main()
{
    unsigned long int x,i, j;
    unsigned prime = 0;
    scanf("%lu", &x);

    char *num = malloc( x);
    if( NULL == num)
    {
        perror( "malloc failed");
        exit(EXIT_FAILURE);
    }


    for(i=0; 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[%lu]\n", i);
        prime++;
      }
    }
     printf("%u\n", prime);
     return 0;
}

数组大小错误

error with array size

c

primes

sieve-of-eratosthenes