Prime Numbers

[LogaTom]

Liebe Forensiker ,
ich bin Neueinsteiger bei Python, also seid gnädig mit mir. Ich muss ein Programm schreiben, das automatisch prime numbers generiert und habe jetzt schon ewig rumgetüftelt, aber leider funktioniert es noch nicht. Wahrscheinlich übersehe ich was Offensichtliches, aber ich wäre froh, wenn mir jemand mal über den Code schauen könnte. Ich weiß, es gibt schon einige Vorschläge für Primzahlengeneratoren, aber ich möchte es ja verstehen und nicht einfach stumpf was kopieren =):

Code: Alles auswählen

Liste = []

for i in range (1,10):
	for j in range (1,i):
		if (i % j == 0):
			Liste += str(j)
			if Liste == []:
				print i 
			del Liste [:]

Mein Grundgedanke war, dass bis zur Primzahl selbst ja keine Division 0 Rest ergeben sollte, wenn es eine Primzahl ist. Deswegen wäre die Liste bei einer Primzahl leer und "i" würde gedruckt. Aber stattdessen bleibt der interaktive Modus einfach leer, spuckt also gar nichts aus =(.
Wäre froh, wenn mir jemand meinen Fehler erklären könnte. Danke im Voraus =).

[BlackJack]

@LogaTom: Überlege mal was Du in Zeile 6 machst, und wie dann der Test in der darauf folgenden Zeile *jemals* wahr sein kann.

Teil das Problem in kleinere Teilprobleme auf. Zum Beispiel in eine Funktion die Testet ob eine gegebene Zahl prim ist oder nicht.

Weder ``+=`` bei Listen noch ``del some_list[:]`` sind idiomatisches Python. Versuche nicht Listen auf diese Art wiederzuverwenden, sondern starte mit einer neuen leeren Liste.

`Liste` ist ein schlechter Name. Der sagt nichts darüber aus was die Elemente im Kontext des Programms bedeuten. Der Sinn der Umwandlung in Zeichenketten erschliesst sich mir auch nicht so recht. Ausser dass das nötig ist, damit ``+=`` funktioniert, was an der Stelle aber auch die falsche Operation ist.

Letztlich brauchst Du aber auch gar keine Liste für diesen Ansatz. Wenn *ein* Teiler gefunden wurde, dann ist die Zahl nicht prim. Und wenn das feststeht sollte man mit der Schleife für die Zahl auch *aufhören* und nicht weitermachen.

Der Ansatz ist sehr ineffizient wenn Du alle Primzahlen in einem Bereich von 1 bis n finden willst. Dafür würde man eher so etwas wie das Sieb des Eratosthenes verwenden.

[heiner88]

@TogaTom: Mit zwei kleinen Änderungen funktioniert dein Programm:
(1x falsch eingerückt) (start mit 2 statt mit 1, weil sonst deine Liste nie leer ist).
Deine Lösung ist (wie BlackJack schon sagte) unidiomatisch und uneffizient.
Du sollest sie mit den Tips von BJack nocheinmal überarbeiten.

Code: Alles auswählen

# python3
Liste = []
for i in range (1,99):
    for j in range (2,i): # start mit 2 statt 1
        if (i % j == 0):
            Liste.append(j)
    if Liste == []:         
       print(i)
    del Liste[:]

[noisefloor]

Hallo,

außerdem braucht man auch wenn nur bis "zu_prüfende_zahl" / 2 prüfen. Wenn man eine natürlich Zahl durch eine Zahl teilt, die grösser als die Hälfte der Zahl ist, kann keine natürliche Zahl als Ergebnis heraus kommen.

Gruß, noisefloor

[jerch]

@noisefloor:

Wenn man eine natürlich Zahl durch eine Zahl teilt, die grösser als die Hälfte der Zahl ist, kann keine natürliche Zahl als Ergebnis heraus kommen.

Eine Zahl durch sich selbst geteilt ergibt 1, was eine natürliche Zahl ist.

außerdem braucht man auch wenn nur bis "zu_prüfende_zahl" / 2 prüfen

Da kann man aber auch noch früher aufhören, überleg mal, wass mit den Faktoren passiert, wenn man die Quadratwurzel überschreitet.

[noisefloor]

Hallo,

Eine Zahl durch sich selbst geteilt ergibt 1, was eine natürliche Zahl ist.

Alle Primzahlen sind durch eins und sich selber teilbar. Von daher: irrelevant,

Gruß, noisefloor

[BlackJack]

@noisefloor: Es mag für das Problem irrelevant sein, aber die Aussage „Wenn man eine natürlich Zahl durch eine Zahl teilt, die grösser als die Hälfte der Zahl ist, kann keine natürliche Zahl als Ergebnis heraus kommen.“ wird deswegen nicht richtig. Gerade bei ”Mathekram” ist Präzision in den Aussagen/Behauptungen ja wichtig.

[jerch]

Bzgl. der Präzision: In meiner Aussage fehlte der Ausschluss der 0.

[Sirius3]

@jerch: Bzgl. der Präzision, welche Zahl muß ich durch welche Zahl teilen, dass das Ergebnis 0 ist?

[jerch]

@Sirius3:
Es geht mir nicht um das Ergebnis, das ist ja auf 1 festgesetzt - sondern die eingesetzte Zahl, die darf nicht 0 sein.

[Sirius3]

@jerch: das Ergebnis ist 1? Welche Zahl erfüllt dann die Gleichung a/0 = 1? Und 0 soll größer sein als die Hälfte einer anderen (positiven) Zahl? Ich verstehe gar nichts mehr.

[noisefloor]

Hallo,

@BlackJack: Im Sinne von "explizit ist besser als implizit" hast du natürlich recht

Gruß, noisefloor

[jerch]

@Sirius3:

Mir ging es um meine eigene Aussage von oben, also n/n = 1, was für alle Zahlen *ausser der 0* gilt. Insofern war meine eigene Aussage unpräzise.

[bwbg]

"Eine Primzahl ist eine Zahl aus der Menge der natürlichen Zahlen (ohne 0), welche genau 2 Teiler besitzt."

"Jede natürliche Zahl (ohne 0) größer 1 (=: neutrales Element) lässt sich als Produkt von Primzahlen und dem neutralen Element darstellen."

Ich hoffe, das ist präzise genug und liefert ausreichend Information für eine Implementierung.