Eratosthenes的筛子

Question

我在解读关于欧拉项目的问题的同时读了Eratosthenes的筛子.我相信你们都知道我在谈论哪个问题.所以这就是事情.我的代码设法正确显示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);