Eratosthenes的筛子

Question

在解决关于Project Euler的问题时，我阅读了Eratosthenes的筛子。我相信你们知道我在谈论哪个问题。 这就是事情。我的代码设法正确显示所有素数低于100万。 但是，当我尝试相同的实现2百万它给了我一个分段错误... 我有一定的想法，为什么错误即将到来，但不知道如何纠正它... 这里是素数的代码低于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]={}; 

四个字节次200万等于8兆字节，这往往是最大堆栈大小。分配不止于此会导致分段错误。

您应该分配在堆的阵列，而不是：

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