arrays - 埃拉托色尼筛法

Question

我在解决关于 Project Euler 的问题时阅读了埃拉托色尼筛法.我相信你们知道我在说哪个问题。所以这就是事情。我的代码设法正确显示了 100 万以下的所有素数。然而，当我为 200 万尝试相同的实现时，它给了我一个段错误......我对为什么会出现错误有一定的了解，但不知道如何纠正它......这是 100 万以下质数的代码。

#include<stdio.h>
int main(void)
{
   int i,k=2;
   int j;
   int n=1000000;
   int prime[2000000]={};
   for(i=0;i<n;i++) // initializes the prime number array
   {
      prime[i]=i;
   }
   for(i=2;i<n;i++) // Implementation of the Sieve
   {
      if(prime[i]!=0)
      { 
         for(j=2;j<n;j++)
         {
            {
               prime[j*prime[i]]=0;
               if(prime[i]*j>n)
                  break;    
            }
         }
      }
   }
   for(i=0;i<n;i++) // Prints the prime numbers
      if(prime[i]!=0)
      {
         printf("%d\n"prime[i]);
      }
      return(0);
   }
}

Answer 1

你在栈中分配了一个巨大的数组:

int prime[2000000]={};

四字节乘以两百万等于八兆字节，这通常是最大堆栈大小。分配超过该数量会导致段错误。

您应该在堆中分配数组，而不是:

int *prime;
prime = malloc(2000000 * sizeof(int));
if(!prime) {
    /* not enough memory */
}
/* ... use prime ... */
free(prime);