Eratosthenes篩C++執行錯誤

Question

我用C++編寫了Eratosthenes篩的這個實現，但是隻要代碼達到59（第16個素數），就停止工作。它只能在舊機器上達到37。當我調試程序時，所有變量似乎都工作正常;該程序只是崩潰。這裏是:(我知道它有很多評論，很多是不必要的。）

// Problem 7:What is the 10 001st prime number? 

/*This program generates a list of prime numbers and uses the Sieve of Eratosthenes to find them. 
*This is done by crossing out multiples of the first known prime (2), taking the first number 
*not yet crossed out, and setting that as the next prime to "sieve" with. 
*/ 

#include "stdafx.h" 
#include <iostream> 

using namespace std; 

int main() 
{ 
    int placeholder;     //added at the end to prevent window from closing 
    const int sieve_size = 10000;  //amount of #s to sieve through 
    const int solution_number = 10001; //# of primes to generate 
    long long solution;     //the 10 001st prime # 
    long long current_sieve;   //current # sieving with 
    int number_of_primes = 1;   //we know the first prime -- 2 
    long long *primes = new long long [number_of_primes]; 
    primes[0] = 2;     //2 is the first prime 
    bool flag_havePrime = 0;  //whether we have our next prime yet; used when saving a prime 
    bool sieve[sieve_size] = {0}; //0 is "could-be-prime" (not composite), 1 is composite. 
    sieve[0] = 1; //0 and 1 are not prime #s 
    sieve[1] = 1; 

    for (int i = 0; number_of_primes <= solution_number; i++) //each loop sieves with a different prime 
    { 
     current_sieve = primes[i]; 

     //This next loop sieves through the array starting with the square of the number we will sieve with, 
     //this optimizes the run time of the program. 
     for (long long j=current_sieve*current_sieve; j <= sieve_size; j++) 
      if (j%current_sieve == 0) sieve[j] = 1; 

     /*This loop gets our next prime by looking through the array until 
     *it encounters a number not crossed out yet. If it encounters a prime, 
     *it increments the number of primes, then saves the new prime into 
     *primes[]. It also prints that prime (for debugging purposes). 
     *The "for" loop ends when it finds a prime, which it knows by encountering 
     *the "havePrime" flag. This needs to be reset before every run. 
     */ 

     for (long long j = primes[number_of_primes-1]+1; flag_havePrime == 0; j++) 
     { 
      if (sieve[j] == 0) 
      { 
       number_of_primes++; 
       primes[number_of_primes-1] = j;    //because array counting starts @ 0 
       cout << primes[number_of_primes-1] << endl; //because array counting starts @ 0 
       flag_havePrime = 1; 
      } 
     } 
     flag_havePrime = 0; //resetting this flag 
    } 
    solution = primes[number_of_primes-1]; //because array counting starts @ 0 
    delete[] primes; 
    primes = 0; 

    cout << "The 10 001st prime number is:\n"; 
    cout << solution << endl; 
    cin >> placeholder; 
    return 0; 
} 

我在想這可能是一個溢出問題？

---

這裏有一個更新的代碼片段，其中只有改變：

const int sieve_size = 500000; 
long long *primes = new long long [solution_number]; 

調試雖然返回一個（喘氣）堆溢出，但在運行編譯版本沒有。編譯後的版本停在104759，重新翻一次。這可能很容易修復。但該程序不打印最後一位，它給你的解決方案。奇怪的。

Answer 1

int number_of_primes = 1;   //we know the first prime -- 2 
long long *primes = new long long [number_of_primes]; 

這將創建一個元素的數組。我很確定你需要比存儲素數更大的東西。

具體而言，只要您開始設置像primes[11]這樣的值（例如），就會進入未定義行爲的範圍。

也許還有你可能要考慮使用在new聲明大小，輕推，輕推，眨眼，眨眼一不同變量，一個點頭的一個眼色爲好瞎馬:-)

---

在代碼中還存在其他一些問題。主要的是你的篩子本身只有10,000個元素。篩的想法是，你需要大量的東西，並篩選出不匹配的東西。對於它的價值，10,001 ^st是105,000以下的觸摸，所以你的篩子應該至少是那麼大。

其次，我見過的人使用數的平方優化發現的因素，但不是以這樣的方式

for (long long j=current_sieve*current_sieve; j <= sieve_size; j++) 
    if (j%current_sieve == 0) sieve[j] = 1; 

你想要的是開始在目前的兩倍篩，並將其添加各時間，是這樣的：

for (long long j = current_sieve * 2; j < sieve_size; j += current_sieve) 
    sieve[j] = 1; 

Answer 2

這裏是一個固定的版本進行比較：

#include <iostream> 
#include <vector> 
#include <string> 

using namespace std; 

int main() 
{ 
    const int sieve_size = 1 << 20; 
    const int solution_number = 10001; 
    int number_of_primes = 0; 
    vector<bool> sieve(sieve_size, true); 

    for (int i = 2; i < sieve_size; i++) 
    { 
     if (!sieve[i]) 
      continue; 

     if (++number_of_primes == solution_number) 
     { 
      cout << "The 10 001st prime number is:" << i << endl; 
      return 0; 
     } 

     for (long long j = i*2; j < sieve_size; j += i) 
      sieve[j] = false; 
    } 
} 

輸出：

The 10 001st prime number is:104743