Fehler beim Versuch, alle Primzahlen von 2 bis n unter Verwendung von Sieat von Eratosthenes in C++ zu finden

Question

Ich muss alle Primzahlen von 2 bis n mit dem Sieb von Eratosthenes finden. Ich schaute auf Wikipedia (Sieve of Eratosthenes), um herauszufinden, was das Sieb des Eratosthenes war, und es gab mir diese Pseudo-Code:

Input: an integer n > 1 

Let A be an array of Boolean values, indexed by integers 2 to n, 
initially all set to true. 

for i = 2, 3, 4, ..., not exceeding √n: 
    if A[i] is true: 
    for j = i2, i2+i, i2+2i, i2+3i, ..., not exceeding n : 
     A[j] := false 

Output: all i such that A[i] is true. 

So habe ich diese und übersetzt es in C++. Es sieht gut aus für mich, aber ich habe ein paar Fehler. Erstens, wenn ich Eingang 2 oder 3 in n, heißt es:

terminate called after throwing an instance of 'Range_error' 
what(): Range_error: 2 

Auch wenn ich 100 oder irgendetwas anderes (4, 234, 149, 22, alles) eingeben, ist es der Eingang für n annimmt, und tut nichts. Hier ist meine C++ Übersetzung:

#include "std_lib_facilities.h" 

int main() 
{ 
/* this program will take in an input 'n' as the maximum value. Then it will calculate 
all the prime numbers between 2 and n. It follows the Sieve of Eratosthenes with 
the algorithms from Wikipedia's pseudocode translated by me into C++*/ 

int n; 
cin >> n; 
vector<string>A; 
for(int i = 2; i <= n; ++i) // fills the whole table with "true" from 0 to n-2 
    A.push_back("true"); 

for(int i = 2; i <= sqrt(n); ++i) 
{ 
    i -= 2; // because I built the vector from 0 to n-2, i need to reflect that here. 
    if(A[i] == "true") 
    { 
     for(int j = pow(i, 2); j <= n; j += i) 
     { 
      A[j] = "false"; 
     } 
    } 
} 

//print the prime numbers 
for(int i = 2; i <= n; ++i) 
{ 
    if(A[i] == "true") 
     cout << i << '\n'; 
} 


return 0; 
} 

Answer 1

Das Problem kommt von der Tatsache, dass die Indizes nicht im Einklang mit dem Wert stehen, den sie darstellen, d. H. Sie werden um 2 nach unten verschoben. Durch diese Operation haben sie nicht mehr die gleichen mathematischen Eigenschaften.

Grundsätzlich befindet sich der Wert 3 an Position 1 und der Wert 4 an Position 2. Wenn Sie für die Division testen, verwenden Sie die Positionen als Werte. Anstatt also zu testen, ob 4% 3 == 0 ist, testen Sie, dass 2% 1 = 0 ist.

Um Ihr Programm Werke zu machen, müssen Sie die -2 Verschiebung des Indizes entfernen:

int main() 
{ 

int n; 
cin >> n; 
vector<string>A; 
for(int i = 0; i <= n; ++i) // fills the whole table with "true" from 0 to n-2 
    A.push_back("true"); 

for(int i = 2; i <= sqrt(n); ++i) 
{ 
    if(A[i] == "true") 
    { 
     for(int j = pow(i, 2); j <= n; j += i) 
     { 
      A[j] = "false"; 
     } 
    } 
} 

//print the prime numbers 
for(int i = 2; i <= n; ++i) 
{ 
    if(A[i] == "true") 
     cout << i << '\n'; 
} 


return 0; 
} 

ich mit anderen Kommentaren zustimmen, können Sie einen Vektor von bools nutzen könnten. Und initialisieren Sie sie direkt mit der richtigen Größe und dem richtigen Wert:

std::vector<bool> A(n, false); 

Answer 2

Hier können Sie zurückzudrängen n-1 Elemente

vector<string>A; 
for(int i = 2; i <= n; ++i) // fills the whole table with "true" from 0 to n-2 
    A.push_back("true"); 

aber hier zugreifen Sie Ihre Vektor von A[2] zu A[n].

//print the prime numbers 
for(int i = 2; i <= n; ++i) 
{ 
    if(A[i] == "true") 
     cout << i << '\n'; 
} 

A hat Elemente an Positionen zu A[0]A[n-2]. Sie können diesen Fehler korrigieren, indem Sie Ihren Vektor anders initialisieren. Zum Beispiel als

vector<string> A(n+1, "true"); 

Dadurch entsteht ein Vektor A mit n+1 Strings mit Default-Werten „true“, die durch A[0] zu A[n] zugegriffen werden kann. Damit sollte Ihr Code laufen, auch wenn er mehr Defizite aufweist. Aber ich denke, Sie lernen am meisten, wenn Sie nur versuchen, das Sieb erfolgreich zu implementieren und dann nach (guten) Alternativen im Internet zu suchen.

Answer 3

Das ist schmerzhaft. Warum verwenden Sie ein String-Array, um boolesche Werte zu speichern, und nicht, sagen wir, ein Array von booleschen Werten? Warum lassen Sie die ersten beiden Array-Elemente weg und erzwingen Sie eine Anpassung aller Indizes? Was vergesst du dann die halbe Zeit, deinen Code komplett zu brechen? Zumindest sollten Sie diese Zeile ändern:

i -= 2; // because I built the vector from 0 to n-2, i need to reflect that here. 

zu:

i -= 2; // because I left the first two elements out, I that here. 
// But only here, doing it everywhere is too annoying. 

Als Ergebnis dieser Design-Entscheidung, wenn Sie diese Zeile aus:

for(int j = pow(i, 2); j <= n; j += i) 

i ist eigentlich Null was bedeutet, dass j für immer Null bleiben wird.