Programm崩潰情況下MAX值太大

我執行Sieve of eratosthenes它工作正常。但是，如果我將MAX值增加到50000之類的應用程序崩潰與未處理的win32異常。我認爲這是因爲一個stackoverflow。Programm崩潰情況下MAX值太大

現在我的問題是如何防止這種情況？

#define MAX 50000 
void Sieb_des_Eratosthenes() 
{ 
    char Zahlen[MAX + 1] = {0}; 
    int i, j, x; 

    for(i = 2; i <= MAX; i++) 
    { 
     if(Zahlen[i] == 0)  
     { 
      Zahlen[i] = 1; 
      for(j = i * i; j <= MAX; j += i) 
      { 
       Zahlen[j] = -1; 
      }  
     } 
    } 
}

我的想法是分配內存，但是，這並不工作

#define MAX 50000 
int Sieb_des_Eratosthenes() 
{ 
    int i, j, x; 
    char *array; 
    array = malloc((MAX + 1) * sizeof(*array)); 
    if (array==NULL) { 
     printf("Error allocating memory!\n"); 
     return -1; //return with failure 
    } 

    for(i = 2; i <= MAX; i++) 
    { 
     if(array[i] == 0)  
     { 
      array[i] = 1; 
      for(j = i * i; j <= MAX; j += i) 
      { 
       array[j] = -1; 
      }  
     } 
    } 
}

來源

2013-04-24 Sir l33tname

'但這並不work' - 你能更具體？你有編譯錯誤嗎？運行時錯誤？意外的結果？ – 2013-04-24 07:29:14

@Andreas我得到了和未處理的win32異常一樣的錯誤 – 2013-04-24 07:32:31

在內部for循環中添加'printf（「％d \ n」，j）;''。在一些迭代超出數組的範圍之後，您會看到j的值爲'-2146737495'。此外，有人建議（同時刪除回答）使用'calloc（）'而不是'malloc（）'，以便數組初始化 - 這是一個非常好的建議，但不修複數組索引問題 – 2013-04-24 07:36:47

失敗雖然所有其他的答案都爲真WRT。實際原因（整數溢出），你只是錯過了維基中僞代碼提供的一些實現細節。以下工作：

使用calloc來分配內存。然後，將所有值初始化爲0，這意味着在wiki僞代碼意義上的true。
在外部循環中，只有循環直到sqrt(MAX) - 請參閱wiki文章中的僞代碼。
在內部循環中，將i的所有倍數標記爲1（在wiki僞代碼意義上的false）。

for(i = 2; i <= sqrt(MAX); i++) { 
    if(array[i] == 0) { // "true" 
     for(j = i*i; j <= MAX; j += i) { 
      array[j] = 1; // "false" 
     }  
    } 
}

然後，這些都是元素仍然0是質數。

此外，沒有必要使用（簽名）int - 所有數字都是正數，所以您應該使用unsigned int。

通過這種方法，你應該能夠使用unsigned int的整個範圍進行MAX值（最多4294967295如果unsigned int是32位）

來源

2013-04-24 08:03:20

你不能做sqrt（MAX）沒有完全理解維基百科的原因，但它是錯誤的 – 2013-04-24 08:37:41

爲什麼？我認爲這是正確的 - 你再次在內循環中使用i^2，所以如果在上一次迭代中'i'是sqrt（MAX），那麼在內循環中以MAX開始。你在內循環中的條件是'j <= MAX'，所以你不會得到任何大於MAX的數字 - 但是如果你使用更大的數字，你會得到的是一個整數溢出。一個不起作用的具體例子？ – 2013-04-24 08:41:27

http://codepad.org/G4MTqxOS試一下，用sqrt（MAX）你只能找到所有素數爲10 – 2013-04-24 08:54:13

一個int只能持有-2^31到2^31最大值： http://en.wikipedia.org/wiki/Integer_(computer_science)

您溢出INT

來源

2013-04-24 07:41:43

你的函數失敗的原始問題是在這個for循環。

for(j = i * i; j <= MAX; j += i)

當我變得等於或大於46349的結果更大i * i溢出和j得到的-2146737495的值，然後在Zahlen[j] = -1;

來源

2013-04-24 07:42:17

我^ 2甚至正確？我們不需要從2 *開始？我看到維基百科僞代碼使用i^2作爲內部循環，但是會不會跳過一些數字來標記？ – 2013-04-24 07:45:41

@Andreas我沒有花時間分析算法的作用，我只檢查可能的錯誤。 – 2013-04-24 07:47:10

只是仔細看了下--i^2以下的數字已經被標記過，所以即使2 * i也應該工作，從i^2開始節省了一些不必要的迭代。此外，直到j <= MAX'，但直到j <= sqrt（MAX） - 纔有必要循環 - 那麼，溢出也應該被避免。 – 2013-04-24 07:51:09

Programm崩潰情況下MAX值太大

回答

相關問題