Sieb des Eratosthenes bricht bei 23 aufgrund eines Segmentation faults ab



  • Hallo liebe Community,

    ich habe die Aufgabe den Sieb des Eratosthenes zu programmieren. Ich habe mich schon soweit wie möglich damit auseinandergesetzt der Code funktioniert an sich auch aber nur für Zahlen kleiner 23 für alle anderen Zahlen wird das Programm abgebrochen. Mit dem Debug Modus habe ich herausgefunden, dass es sich um einen Segmentation faults handelt. Was kann ich an meinem Code verändern, damit dieser Fehler verschwindet?

    #include <iostream>
    #include <math.h>

    using namespace std;

    int main()
    {

    int n;              //Grenze des zu betrachtenden Bereichs
    int x = 2;
    
    
    cout << "Geben Sie den Wertebereich ein fuer die Sie die Primzahlen herausbekommen moechten." << endl;
    cin >> n;
    if (n<2) {                                                              //n soll nicht kleiner 2 sein, wenn doch wird n solange eingelesen bis es größer 2 ist
        cout << "Geben Sie den Wertebereich ein fuer die Sie die Primzahlen herausbekommen moechten." << endl;
        cin >> n;
    } else {
    
    
    
    
    int Zahlen[n-1];                        //Array Zahlen mit der Größe n-1, da wir die 1 nicht betrachten
    
    for(int i = 0; i<n-1; i++){             // Schleife füllt Array mit Zahlen x=2 bis n
        Zahlen[i] = x;
        x++;
    }
    
    
    for(int g=0;g<n-1;g++) {                
    if(Zahlen[g] != -1) {                   //Wenn Array an der Stelle g ungleich -1(-1 steht für durchgestrichen) dann wird die Zahl an der Stelle g in den Buffer geladen
        int buffer = Zahlen[g];             
        while(buffer<n-1){                  //Solange buffer sich nicht außerhalb des Arrays befindet
            Zahlen[g+buffer] = -1;          //Werden alle Vielfachen von Zahl G "durchgestrichen"
            buffer += Zahlen[g];            //buffer wird um Zahl an der Stelle G erhöht
        }
    
    } else {
        Zahlen[g] = -1;                     // Falls schon Zahl an der Stelle G durchgestrichen ist wird diese nochmal durchgestrichen
    
    }
    }
    
    
    for(int s = 0; s<n-1; s++){             //Gibt den Array aus
        cout << Zahlen[s] << "\t";
    
    }
    

    }
    }

    Freue mich auf eure Hilfe 😉



  • Schreibe bitte in eine Zeile vor Deinem Code ``` und in eine Zeile nach Deinem Code ```. Alternativ markiere Deinen Code und klicke auf das </> in der Symbolleiste über dem Eingabefeld.
    Du kannst Deine Beiträge auch im Nachhinein noch bearbeiten. Den Menüpunkt "Bearbeiten" findest Du in dem Drei-Punkte-Menü rechts unter Deinen Beiträgen.
    Danke.



  • Es gibt in C++ keine Variable Length Arrays und die Größe des Arrays muss zum Übersetzungszeitpunkt bekannt sein. Wenn Du hier die Compilerflags für die Einhaltung der Norm aktiviert hättest, gäbe es auch den passenden Fehler.

    Stattdessen solltest Du #include <vector> bei den Includes ergänzen und anstatt int Zahlen[n-1]; die Anweisung std::vector<int> Zahlen(n-1); nutzen. Es ist noch immer ein Speicherfehler drin. Den solltest Du selbst finden.

    #include <iostream>
    #include <cmath>
    #include <vector>
    #include <cstdlib>
    
    using namespace std;
    
    int main() {
        // Grenze des zu betrachtenden Bereichs
        int n;
        int x = 2;
    
    
        cout << "Geben Sie den Wertebereich ein fuer die Sie die Primzahlen herausbekommen moechten." << endl;
        cin >> n;
    
        // n soll nicht kleiner 2 sein, wenn doch wird n solange eingelesen bis es größer 2 ist
        if (n < 2) {
            cout << "Geben Sie den Wertebereich ein fuer die Sie die Primzahlen herausbekommen moechten." << endl;
            cin >> n;
    
            return EXIT_FAILURE;
        }
    
        // Array Zahlen mit der Größe n-1, da wir die 1 nicht betrachten
        std::vector<int> Zahlen(n-1);
    
        // Schleife füllt Array mit Zahlen x=2 bis n
        for (int i = 0; i < (n-1); i++) {
            Zahlen[i] = x;
            x++;
        }
    
    
        for (int g = 0; g < (n-1); g++) {
            // Wenn Array an der Stelle g ungleich -1(-1 steht für durchgestrichen) dann wird die Zahl an der Stelle g in den Buffer geladen
            if (Zahlen[g] != -1) {
                int buffer = Zahlen[g];
    
                // Solange buffer sich nicht außerhalb des Arrays befindet
                // Werden alle Vielfachen von Zahl G "durchgestrichen"
                // buffer wird um Zahl an der Stelle G erhöht
                while (buffer < (n-1)) {
                    Zahlen[g+buffer] = -1;
                    buffer += Zahlen[g];
                }
            } else {
                // Falls schon Zahl an der Stelle G durchgestrichen ist wird diese nochmal durchgestrichen
                Zahlen[g] = -1;
            }
        }
    
        // Gibt den Array aus
        for (int s = 0; s < (n-1); s++) {
            cout << Zahlen[s] << "\t";
        }
    
        return EXIT_SUCCESS;
    }
    


  • Hallo John ich hätte gerne mit Vektoren gearbeitet, uns wurde jedoch vorgegeben mit Arrays zu arbeiten. Wie kann ich den Fehler umgehen und trotzdem Arrays nutzen. Danke swordfish für deinen Tipp. Ich werde es mir fürs nächste Mal merken.



  • Dann musst Du ein Array mit vorgegebener Größe definieren, und dann darauf testen, ob die Arraygröße für die Eingabe ausreicht. Wenn es Dir erlaubt ist, kannst über new[] und delete[] mit Pointer passenden Felder anlegen, aber …

    Warum muss man so einen Sch*** in Vorlesungen/Übungen machen?



  • Frag mich das nicht :). Also führt nichts an dem Fehler vorbei?



  • @FirebladeRR sagte in Sieb des Eratosthenes bricht bei 23 aufgrund eines Segmentation faults ab:

    Frag mich das nicht :). Also führt nichts an dem Fehler vorbei?

    @john-0 sagte in Sieb des Eratosthenes bricht bei 23 aufgrund eines Segmentation faults ab:

    Es ist noch immer ein Speicherfehler drin. Den solltest Du selbst finden.



  • Es gibt noch immer einen Fehler in Deinem Programm, selbst wenn man es mit vector umsetzt. Man findet solche Fehler leicht, wenn man einen Debugger benutzt. Hast Du das noch nie gemacht?



  • Also den Debugger habe ich bereits benutzt nur weiß ich nicht wie ich einen Speicherfehler damit ausfindig machen soll. Ich habe damit nur herausgefunden, dass es sich um einen Segmentation Fehler handelt.



  • Wie kann man das Problem finden?

    • Variante 1: Du startest das Programm im Debugger und gehst Schritt für Schritt durch. Bei irgendeiner Zeile tritt dann der Fehler auf. Oder du lässt das Programm laufen und wartest, bis dir der Debugger den Fehler anzeigt. Wie das genau geht, hängt vom Debugger ab.
    • Variante 2: Mit Address-Sanitizer kompilieren, hier bezogen auf die von @john-0 gepostete Code-Variante:
    g++ -Wall -Wextra -g -Og -fsanitize=address prim.cpp && ./a.out
    

    Das Programm läuft dann so:

    Geben Sie den Wertebereich ein fuer die Sie die Primzahlen herausbekommen moechten.
    100
    =================================================================
    ==11287==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x6140000001dc at pc 0x56064feaf953 bp 0x7fff1ec3cfa0 sp 0x7fff1ec3cf90
    WRITE of size 4 at 0x6140000001dc thread T0
        #0 0x56064feaf952 in main /tmp/prim.cpp:44
        #1 0x7fae0e0b90b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
        #2 0x56064feaf36d in _start (/tmp/a.out+0x236d)
    (und weitere Ausgabe)
    

    Der Fehler ist also in /tmp/prim.cpp:44 (also Zeile 44).
    Da steht Zahlen[g+buffer] = -1;. Also wird g + buffer hier wohl nicht im erlaubten Bereich liegen.

    Was ist buffer? Was ist g? Liegt die Summe sicher im Bereich [0, n-1)?



  • @FirebladeRR
    Neben dem was wob geschrieben hat, möchte ich noch anmerken, dass auch deine Grenze in der for Schleife

    for(int g=0;g<n-1;g++) 
    

    verdächtig aussieht.

    Lies dir mal den Wiki Artikel Sieb des Eratosthenes durch.



  • Ok, danke ich werde mich, sobald ich zu Hause bin wieder dransetzen und hoffentlich das Problem lösen.



  • Danke an alle Helfer habe mir noch mal den Wiki Artikel durchgelesen und alles von neu programmiert statt am alten Programm festzuhalten. Es funktioniert jetzt.



  • @FirebladeRR sagte in Sieb des Eratosthenes bricht bei 23 aufgrund eines Segmentation faults ab:

    Danke an alle Helfer habe mir noch mal den Wiki Artikel durchgelesen und alles von neu programmiert statt am alten Programm festzuhalten. Es funktioniert jetzt.

    Poste es gerne, wenn du Verbesserungsvorschläge bekommen willst.


Log in to reply