Eratosthenes實現的篩

Question

我想實現Eratosthenes Sieve的算法，但我不知道爲什麼這個程序崩潰的大型項目。最初我使用vector，但現在我正在使用動態內存分配來實現這一點。

#include<iostream> 
#include<cmath> 
#include<cstdlib> 
using namespace std; 

unsigned isqrt(unsigned value) { 
    return static_cast<unsigned>(sqrt(static_cast<float>(value))); 
} 

int main() 
{ 
    int t; 
    cin >> t; 
    long long * N; 
    long long * M; 
    long long n, m; 
    N = new long long[t]; 
    M = new long long[t]; 
    for(int i = 0; i < t ; i++){ 
     cin >> M[i] >> N[i]; 
    } 

    for(int i = 0; i < t ; i++){ 
     n = N[i]; 
     m = M[i]; 

     bool * A; 
     A = new bool[n]; 
     if(A == 0) 
     { 
      cout << "Memory cannot be allocated"; 
      return 0; 
     } 

     for(int i=0;i < n;i++){ 
      A[i]=true; 
     } 
     A[0] = false; 
     A[1] = false; 

     unsigned sqrt = isqrt(n); 
     for(int i = 2; i <= sqrt; i++) 
     { 
      if(A[i] == true){ 
       for(int j = i*i; j <= n; j = j + i) 
       { 
        A[j] = false; 
       } 
      } 
     } 

     for(int i = m;i < n;i++) 
     { 
      if(A[i] == true) 
       cout << i << "\n"; 
     } 

     delete[] A; 
    } 

    delete[] M; 
    delete[] N; 
    return 0; 
} 

程序崩潰對於較大的n和m（〜10^16）值。請幫助我。

Answer 1

for(int j = i*i; j <= n; j = j + i) 
        ^^ 

如果j == n然後A[j] = false將分配給過去陣列的端部的元素。測試應該是j < n。

Answer 2

在調試器中運行以確定崩潰的位置並從那裏進行調試。這一點很可能會很明顯。

您可以從IDE或從命令行執行此操作。在後一種情況下編譯-g並運行程序，如gdb。谷歌的東西像「gdb cheatsheet」開始。

Answer 3

如果n大到足以引起內存分配錯誤，程序將會崩潰，由於不正確的內存分配的錯誤處理

A = new bool[n]; 
     if(A == 0) 
     { 
      cout << "Memory cannot be allocated"; 
      return 0; 
     } 

新的錯誤不返回0，但拋出的std :: bad_alloc的那並不是」 t會被捕獲，這反過來會導致意外（），然後終止（），最後abort（）被調用。
正確的版本是：

try 
    { 
    A = new bool[n]; 
    } 
    catch (std::bad_alloc& ba) 
    { 
    std::cerr << "Memory cannot be allocated: " << ba.what() << '\n'; 
    } 

Answer 4

如果你打算寫埃拉托色尼在C++篩子，怎麼樣，如果你確實使用 C++，不要試圖把它當作C的一些瘋狂的交叉和彙編語言。

#include <vector> 
#include <iostream> 

unsigned long primes = 0; 

int main() { 
    int number = 10000000; 
    std::vector<bool> sieve(number,false); 
    sieve[0] = sieve[1] = true; 

    for(int i = 2; i<number; i++) { 
     if(!sieve[i]) { 
      ++primes; 
      for (int temp = 2*i; temp<number; temp += i) 
       sieve[temp] = true; 
     } 
    } 
    std::cout << "found: " << primes << " Primes\n"; 
    return 0; 
}