Keine Ausgabe bei neuer Art der Implementierung des Siebes von Eratosthenes

[hansjürgen]

Hallo liebe Forenmitglieder,
Ich implementiere das Sieb des Eratosthenes auf eine Art und Weise,die Ich bis jetzt auch nach längerer Recherche nicht gefunden habe.
Ich habe in diesem Forum viele Implementierungen gesehen,welche True und False genutzt haben,da Ich,jedoch ein blutiger Anfänger bin habe Ich da nicht durchgeblickt.Erst recht nicht bei den Optimierungen des Siebes von Eratosthenes.Deshalb möchte Ich eine Art der implementierung machen,welche sich die Positionen der Zahlen innerhalb der Liste zunutzemacht.

Code: Alles auswählen

def sieb_des_eratosthenes(obere_Grenze):
    a = list(range(2, obere_Grenze + 1))
    # Erstellt eine Liste potenzieller Primzahlen
    teiler = a[0]
    # Der Teiler ist die kleinste Zahl in der Liste
    while a.index(teiler) != -1:
        # Die Schleife bricht ab,wenn die größte Zahl eine Primzahl ist
        while obere_Grenze > teiler:
            if obere_Grenze % teiler == 0:
                del a[a.index(obere_Grenze)]
            # durchläuft alle Zahlen in der Liste
            obere_Grenze -= 1
            # Der Teiler ist die nächste Primzahl bzw. die nächstgrößere
        teiler = a[0 + 1]
    return a

# Testlauf
sieb_des_eratosthenes(20)

Nun bekomme Ich jedoch nix bei der Ausgabe.Meine Frage lautet nun: Was ist der Fehler im Porgramm,welcher dafür sorgt,dass keine Ausgabe ausgegeben wird ?

[Sirius3]

@hansjürgen: vielleicht findest Du diese Art der Implementierung nicht, weil sie nicht funktioniert. Es ist auch schwierig, eine Zeile zu nennen, wo ein Fehler ist, weil alles nicht ganz so zusammenpasst. Du benutzt auch nicht die Position innerhalb der Liste, das tun viele andere Verfahren.

Nachdem beim ersten Durchlauf der äußeren Schleife `obere_Grenze` bei 2 angekommen ist, wird teiler auf 3 gesetzt und die innere Schleife nicht mehr durchlaufen. Und 3 ist in `a` enthalten, Du bekommst also eine Endlosschleife.

Schau Dir nochmal das Sieb genau an und versuche Dich genau an die Anleitung zu halten; spiele das mal mit Papier und Bleistift durch. Erst wenn Du genau verstanden hast, wie es funktioniert, und Du das exakt so in Python umgesetzt hast, kannst Du Dir eine eigene (bessere) Methode überlegen.

PS: Wenn Du eine Prüfung auf Teilbarkeit hast, dann hast Du kein Sieb.

[hansjürgen]

PS: Wenn Du eine Prüfung auf Teilbarkeit hast, dann hast Du kein Sieb.

Auf welche Art und Weise soll Ich dann die Vielfachen der Zahlen herausfinden ?

Schau Dir nochmal das Sieb genau an und versuche Dich genau an die Anleitung zu halten; spiele das mal mit Papier und Bleistift durch

Das habe Ich gemacht,jedoch weiss Ich nicht wie man in Python Zahlen 'markieren' kann ?

Code: Alles auswählen

def sieb_des_eratosthenes(obere_Grenze):
    Liste_mit_moeglichen_Primzahlen = list(range(2,obere_Grenze+1))
    # erstellt eine Liste mit allen möglichen Primzahlen bis zur oberen Grenze
    teiler = min(Liste_mit_moeglichen_Primzahlen)
    # Der Teiler ist am Anfang der kleinste Wert innerhalb einer Liste
    while teiler != max(Liste_mit_moeglichen_Primzahlen):
        # Die Schleife wird solange iteriert bis der Teiler,welcher immer eine Primzahl ist,der größte Wert innerhalb einer Liste ist
        for i in Liste_mit_moeglichen_Primzahlen[Liste_mit_moeglichen_Primzahlen.index(teiler)+1:-1]:
            if i%teiler == 0:
                # Der Teiler überprüft nun bei allen Zahlen innerhalb der Liste bis auf sich selbst ob sie vielfache von ihm sind.
                del Liste_mit_moeglichen_Primzahlen[Liste_mit_moeglichen_Primzahlen.index(i)]
                # Wenn eine Zahl in der Liste eine vielfache von dem Teiler ist wird sie aus der Liste durchgestrichen
        s = 1
        teiler = Liste_mit_moeglichen_Primzahlen[0+s]
        #Der Teiler nimmt nun den nächstgrößeren Wert innnerhalb der Liste ein
        s += 1
        # Das Problem was Sirius mit der Endlosschleife angesprochen hat wird mithilfe der Variabel s behoben
    return Liste_mit_moeglichen_Primzahlen
sieb_des_eratosthenes(20)

Jedoch bekomme in der Ausgabe wieder nichts,obwohl das Problem mit der Endlosschleife behoben wurde

[Sirius3]

@hansjürgen: da mitten drin ein `s = 1` steht, hast Du immer noch ein Endlosschleife. Außerdem ist 20 keine Primzahl. Warum sparst Du die letzte Zahl der Liste immer aus? Fehlt Dir nur `print` damit das Ergebnis ausgegeben wird?

Nimm Dir ein Blatt Papier und gehe nach Anleitung vor (wie sie z.B. bei Wikipedia wunderbar beschrieben).

Dann versuche das in Python umzusetzen.

Dein jetziges Verfahren ist deutlich ineffizienter als das durchprobieren aller bereits gefundenen Primzahlen:

Code: Alles auswählen

def find_primes(ende):
    primes = [2]
    for i in range(3, ende + 1):
        if not any(i % p == 0 for p in primes):
            primes.append(i)
    return primes

[hansjürgen]

Ich bin jetzt zur Erkenntnis gekommen,dass mein Ansatz viel zu kompliziert und ineffizient ist.
Deshalb habe Ih mir ein Video dazu angeschaut und habe nun verstanden wie man die Vielfachen einer Zahl effizient bestimmen kann.

Code: Alles auswählen

def sieb_des_eratosthenes(s):
    prim = []
    Tabelle = list(range(2,s))
    c = 2
    while c*c < s:
        for i in range(c,s,c):
            if i in Tabelle:
                Tabelle.remove(i)
        prim.append(c)
        c = Tabelle[0]
    return prim+Tabelle

Vielen Dank für eure Hilfe,welche mir gezeigt hat,dass die Grundidee meines Programms ineffizient ist.