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);