在C++初始化數組時出現Seg錯誤（項目歐拉數3）

所以我試圖編寫一個程序來解決項目歐拉問題上最大的素因子，而我知道代碼在結構上是正確的（只要它返回正確答案爲較小的數字，包括例如13195，他們給），I保持在接收時I輸入我們應該數量來解決，這是一個分段錯誤600851475143.的代碼如下：在C++初始化數組時出現Seg錯誤（項目歐拉數3）

#include <stdio.h> 
#include <math.h> 

main(){ 
    int number,a,b,c,i,j,n,gpf; 
    printf("Input number to analyze: "); 
    scanf("%d",&number); 
    a = number/2; 
    printf("%d\n",a); 
    int* primesieve = new int[a+1];    /*IMPORTANT LINE*/ 
    for (i=0;i<a+1;i++){ 
     primesieve[i] = 1; 
    } 
    for (j=2;j<=a;j++){ 
     if (primesieve[j] == 1){ 
      for (c=2;j*c<=a;c++){ 
       primesieve[j*c] = 0; 
      } 
     } 
    } 
    for (n=2;n<=a;n++){ 
     b = number/n; 
     printf("%d\n",b); 
     if (number % n == 0){ 
      if (primesieve[b] == 1){ 
       gpf = b; 
       n = a+1; 
      } 
     } 
    } 
    delete[] primesieve; 
    printf("The greatest prime factor of %d is %d.\n",number,gpf); 
}

的問題來自初始篩選數組的初始化，因爲我忽略了之後的所有行並仍然遇到問題。我最初使用下面的代碼聲明瞭該數組，該代碼爲低至1000萬的值返回了分段錯誤。

int primesieve[a+1];

我搜索了這個網站，它產生的變化來動態數組分配一個解決方案，但在這個問題解決了10億美元，它顯然沒有對顯著較大的值。我注意到的其他解決方案提到了有關使用malloc（）或在main（）之外靜態聲明數組的問題，但坦率地說我並不瞭解這些，因爲我的入門級編程類幾乎沒有提及malloc（），我認爲導致聲明的代碼數組需要包含在main（）中。（作爲參考：Segmentation Fault While Creating Large Arrays in C和Seg Fault when initializing array。）我確定這是一個相當簡單的問題，但我是一個相對較新的程序員，因此對分配內存的理解很差，因此對其他解決方案的任何建議，解決方案或解釋我發現將不勝感激。

來源

2013-10-19 Arnold Myers

好的，所以你們都說在「普通」電腦上有這麼大的篩子是不可能的？既然我不打算讓高端電腦回答一個歐拉項目問題，是否有更好的方法來處理超過偶數的位圖和省略的篩選？也許是零碎的？編輯：我應該提到這一點上面 - 我在Vista 4 64GB，並通過Cygwin運行該程序。 –

好的，我發現篩網對於這個數量級來說是不可行的。我會嘗試一種不同的方法，即使這種算法明顯適用於較小的數字。感謝下面給出的每個答案。 –

如果你打算編碼C++，我會強烈建議你看看[書目列表]（http://stackoverflow.com/a/388282/332733） – Mgetz

您的經驗與編譯器的物理限制和精度有關。第一次嘗試中，堆疊

int primesieve[a+1];

快速失敗上分配陣列，因爲在大多數系統中堆疊尺寸是相當有限的相比堆。

在堆上分配

int* primesieve = new int[a+1];

爲您提供了更多的空間，但你仍然有可尋址內存的限制。現在，600851475143是一個相當大的數字，即使將它除以2也是如此。假設int的大小是4個字節，那麼您是否真的可以解決這個問題？使用32位，您可以尋址2^32 = 4294967296字節。

來源

2013-10-19 10:00:01

溢出！

它不能在您的內存中分配陣列大小600851475143。在32位系統中，它需要4,476 GB。

來源

2013-10-19 09:41:39 deepmax

600851475143 * sizeof(int64_t) = 4806811801144 = 4.4TB

換句話說，除非你有5TB的RAM，否則這段代碼將一直崩潰。

如果您使用位圖篩選，則可以使其更易於使用。例如，每個數字使用1位，而不映射偶數只需要600851475143/8/2 = 35GB的RAM。還有很多，但如果你有一些硬件的錢可行。

來源

2013-10-19 09:42:20 mvp

在C++初始化數組時出現Seg錯誤（項目歐拉數3）

回答

相關問題