Das deutsche Python-Forum

darktrym hat geschrieben:Du hast eine Liste aller gefunden Primzahlen bis n.
Also müsste jede weitere Zahl(n+1), sofern sie eine Primzahl ist, nicht teilbar sein durch Elemente aus dieser Liste.

cofi hat geschrieben:Stichwort: Sieb des Erastothenes.

Wie du testest ob eine Zahl prim ist, ergibt sich aus der Definition: Sie ist nur durch sich selbst und 1 restlos teilbar. Die naive Loesung ist also eine Schleife in einer Schleife zu benutzen. Mit ein paar Optimierungen ist man dann schnell an erwaehntem Algorithmus.

primliste = [2]
    teiler = 1
    for zahl in range(2,n//2):
            while teiler <= zahl // 2:
                teiler = teiler + 1
                if zahl % teiler == 0:
                    continue
                primliste.append(zahl)

if zahl % teiler == 0:
                    continue

darktrym hat geschrieben:Okay,
du hast eine Liste mit einem Element 2.

Nun testet du ob:
3 - kein Teiler, also prim, ab in Liste(2,3)
4 - hat 2 als Teiler, entsorgen
5 - kein Teiler, ab in Liste(2,3,5)
6 - Teiler 2, entsorgen
7 - kein Teiler, ab in Liste(2,3,5,7)
8 - Teiler 2, entsorgen
9 - Teiler 3, entsorgen
...

Du siehst man muss eigentlich nur jedes 2. Element untersuchen und bis maximal Wurzel n gehen.
Der Algorithmus ist primitiv (und ineffient).

primliste = [2]
    teiler = 1
    for zahl in range(3,n//2):
            while teiler <= zahl / 2:
                teiler = teiler + 2
                if zahl % teiler == 0:
                    break
                primliste.append(zahl)
    return primliste

darktrym hat geschrieben:Du musst schon prüfen ob die zu untersuchende Zahl auch ja keinen Teiler hat in der Liste deiner bereits gefunden Primzahlen.
Im Prinzip zwei in sich geschachtelte for-Schleifen, die äußere iteriert über alle Zahlen, die innere über die Elemente aus primliste. Die Abbruchbedingung hast du bereits richtig erkannt.

    primliste = [2]
    teiler = 1
    for zahl in range(3,n//2):
            while teiler <= zahl / 2:
                teiler = teiler + 2
                for listenteiler in primliste:
                    if zahl % listenteiler == 0:
                        break
                if zahl % teiler == 0:
                    break
                primliste.append(zahl)
    return primliste

webspider hat geschrieben:Passend eingestreute print-Anweisungen sind ebenfalls eine primitive, aber sehr hilfreiche Debuggingmethode.

darktrym hat geschrieben:

Code: Alles auswählen

primes = [2]
last = int(input("number: "))
for number in xrange(3, last, 2):
    (?1)
    for test in primes:  
        if number % test  == 0:
            (?2)
            break
    if (?3):
        primes.append(number)
print primes     

Ich habs so gelöst, nun musst du nur noch die Fragezeichen klären

darktrym hat geschrieben:1.) Klar doch.
2.) Ersetze mal die Fragezeichen durch print Anweisungen. Und probier's mal mit Eingabe von 30.

EyDu hat geschrieben:Du sollst dir die Zwischenergebnisse ausgeben lassen, so siehst du, was du falsch gemacht hast.

Zu dem if: for-Schleifen kann man noch einen else-Block anfügen, welcher genau dann ausgeführt wird, wenn man die Schleife nicht mit break verlassen hat. Jetzt kannst du dir ja mal überlegen, was das mit deinem Fall zu tun hat.

    primliste = [2]
    for zahl in range(3,n,2):
        for teiler in primliste:
            print(primliste)
            if zahl % teiler == 0:
                print(primliste)
                break
        if print(primliste):
            primliste.append(zahL)
        return primliste