1

我实施了 Eratosthenes 筛法，效果很好。但是，如果我将 MAX 值增加到 50000 之类的值，则应用程序崩溃并出现未处理的 win32 异常。我认为这是因为堆栈溢出而发生的。

现在我的问题是如何防止这种情况发生？

#define MAX 50000
void Sieb_des_Eratosthenes()
{
    char Zahlen[MAX + 1] = {0};
    int i, j, x;

    for(i = 2; i <= MAX; i++)
    {
       if(Zahlen[i] == 0)     
       {
           Zahlen[i] = 1;
           for(j = i * i; j <= MAX; j += i)
           {
                 Zahlen[j] = -1;
           }      
       }
    }
}

我的想法是分配内存，但这不起作用

#define MAX 50000
int Sieb_des_Eratosthenes()
{
    int i, j, x;
    char *array;
    array = malloc((MAX + 1) * sizeof(*array));
    if (array==NULL) {
       printf("Error allocating memory!\n");
       return -1; //return with failure
    }

    for(i = 2; i <= MAX; i++)
    {
       if(array[i] == 0)     
       {
           array[i] = 1;
           for(j = i * i; j <= MAX; j += i)
           {
                 array[j] = -1;
           }      
       }
    }
}
4

3 回答 3

3

您的函数失败的原始问题是在这个 for 循环中。

for(j = i * i; j <= MAX; j += i)

当 i 等于或大于 46349 时，结果i * i溢出并且 j 获取值-2146737495然后失败Zahlen[j] = -1;

于 2013-04-24T07:42:17.300 回答
1

一个 int 最多只能容纳 -2^31 到 2^31： http://en.wikipedia.org/wiki/Integer_(computer_science)

你溢出了int

于 2013-04-24T07:41:43.903 回答
1

虽然所有其他答案都是正确的。实际原因（整数溢出），您只是错过了 wiki 中伪代码提供的一些实现细节。以下作品：

  • 用于calloc分配内存。然后，所有值都被初始化为wiki 伪代码意义上的0意思true。
  • 在外循环中，仅循环直到sqrt(MAX)- 请参阅 wiki 文章中的伪代码。
  • 在内部循环中，i用1（false在维基伪代码的意义上）标记所有倍数。
for(i = 2; i <= sqrt(MAX); i++) {
   if(array[i] == 0) { // "true"
       for(j = i*i; j <= MAX; j += i) {
             array[j] = 1;  // "false"
       }      
   }
}
  • 然后，所有仍然0是素数的元素。

另外，没有必要使用 (signed) int- 所有数字都是正数，所以你应该使用unsigned int.

使用这种方法，您应该能够将整个范围unsigned int用于MAX值（直到4294967295ifunsigned int是 32 位）

于 2013-04-24T08:03:20.633 回答