[Python] Hilfe bei Implementierung eines Prim-Alogrithmus [erledigt]

D

Darillian

0
Die in der Python-Dokumentation erwähnte Implementierung einer Prim-Überprüfung (Link) ist zwar sehr gut nachvollziehbar, allerdings bei großen (ca. ab 10^6) Zahlen sehr ressourcenfressend und vor allem langsam. Daher wollte ich, um Übung in Python zu kriegen folgenden Code optimieren:
Code: 
for x in range (20000,21000):
     for n in range(2, x):
          if x % n == 0:
               break
     else:
          print 'Primzahl gefunden!', x)

Ich habe daran gedacht, die zweite Zeile, also das Erstellen einer "Teilerliste" durch eine echte Teilerliste nur mit Primzahlen zu ersetzen. Allerdings habe ich Probleme, die gefundene Primzahl global an "teiler" anzufügen, dies geschieht immer nur lokal in der else:-Option:
Code: 
for x in range(20000,21000):                     #Das Intervall, das nach Primzahlen durchsucht werden soll
     teiler = [2]                                #Teilerliste (Inhalt sind nur Primzahlen)
     for n in teiler:
          if x % n == 0:                         #Falls die aktuell untersuchte Zahl (x) durch ein Element der Teiler-Liste restlos teilbar ist, ist x nicht prim
               break
     else:
          print 'Primzahl gefunden!', x
          teiler.append(x)                       #Falls eine Primzahl gefunden wird, soll sie ans Ende der Teilerliste angehängt werden
          print teiler                           #Ausgabe der Teilerliste um zu prüfen, ob sie korrekt geändert wurde

Nun ist allerdings das Problem, dass ich keinen Schimmer habe, wie ich "teiler" global ändern kann. Wenn ich den oberen Code durchlaufen lasse, bekomme ich folgende Ausgabe:
Code: 
Primzahl gefunden! 20001
[2, 20001]
Primzahl gefunden! 20003
[2, 20003]
Primzahl gefunden! 20005
[2, 20005]
usw.
Ich hoffe, jemand kann mir eine simple Antwort darauf geben und schüttet mich nicht mit alternativen Implementierungen dieses Problems zu ;)
 
Hallo Darillian,

der Fehler liegt darin, dass du teiler bei jedem Schleifendurchlauf [2] erneut zuweist und die Werte somit nach jede Schleifendurchlauf verworfen werden.
Code: 
teiler = [2]
muss also noch vor der ersten Schleife stehen, und dann funktioniert's auch.
 
Um antworten zu können musst du eingeloggt sein.
Zurück
Oben