Frage von IronDetektiv, 210

Primzahlen in Python ausgeben?

Hallo, bin Programmier-Anfänger und stelle mich ziemlich doof an. Im Folgenden ist ein Programm, das Primzahlen generiert. Ich verstehe aber nicht was der Computer mach, auch wenn das Programm sehr einfach ist. Kann mir einer an den Primzahlen "2, 3, 5" konkret erklären, was da ausgerechnet wird?

p=2

while True:

  t=2
    
  while p%t !=0 and t<p:
        
     t= t+1
   
  if t==p:
        
     print p
    

p=p+1

Antwort
von sarahj, 160

nun, es dividiert ("p%t") durch alle kleineren Zahlen ("while t<p"), bis eine gefunden wird, bei der Rest == 0 raus kommt (also teilbar ist).
Wenn die Schleife beendet ist, UND dann t == p ist, wurde keine gefunden.
Wurde eine gefunden, so wird die Schleife mit t != p enden.

Also ist p eine Primzahl wenn t==p, und wird ausgegeben.

Das Programm ist allerdings ziemlich dumm geschrieben, und wohl der schlechteste Primzahl-Prüf-Algorithmus, den ich seit langem gesehen habe. Er funktioniert, ist aber höchst ineffizient.

Du kannst Dir ein paar Fragen selbst stellen:

1) welches ist wohl die größte Zahl, die p noch ohne Rest teilen würde? Muss man wirklich t bis p laufen lassen, oder kann man vorher aufhören-? Wenn ja, wo?
2) schon allein das Überspringen aller geraden t reduziert die Anzahl der Prüfungen um die Hälfte. Macht also das Programm doppelt so schnell.
Könntest Du Dir vorstellen, welche Zahlen überhaupt als Teiler zu prüfen sind?
(i.e. angenommen p ist nicht durch t teilbar, macht es dann Sinn, 2*t, 3*t, usw. zu versuchen?)

Kommentar von Machtnix53 ,

Wenn man Modulo von 6 berechnet, muss beispielsweise nur bei 1 und  5 weiter getestet werden, da sie bei 0,2,3,4 durch 2 oder 3 teilbar ist. Für schnelleres Testen von großen Primzahlen kann man auch %30 (6*5) ,%210 (30*7) usw verwenden.

Sinnvoll ist es auch die gefundenen Primzahlen aufzulisten, um sie in Tests wiederzuverwerten. 

Kommentar von Schachpapa ,

Zu 2)

Du willst wahrscheinlich darauf hinaus, dass das Prg. nur Primzahlen als Teiler probieren soll. Dann müsste es aber entweder eine Liste aller Primzahlen führen oder jeweils für die mögl. Teiler prüfen, ob sie prim sind. Dann ist es aber einfacher, durch den nichtprimen Teiler zu teilen, obwohl das Ergebnis schon bei den Teilern des Teilers gefunden wurde.

Am Beispiel: Statt zu prüfen, ob ich mir das Teilen durch 91 sparen kann, weil 91 eventuell nicht prim ist, teile ich einfach und stelle fest "teilt nicht" (wenn vorher schon 7 und 13 nicht teilten).

Kommentar von sarahj ,

wollte eigentlich den Gedanken in Richtung Sieb anstoßen.
Da werden ja auch Vielfache rausgestrichen...

Aber ja; man kann auch eine Liste der PrimZahlen halten
(es reicht eine Tabelle der Primzahlen bis zu einer bestimmten Größe, z.B. aller Primzahlen bis 1000. Die benötigt nur 168 Integer-Plätze und könnte statisch definiert oder dynamisch generiert werden).
Damit spart man schon eine Unmenge Divisionen.

Die macht sich natürlich bei kleinen Zahlen wenig bemerkbar;
aber wie lange dauert folgende Abfrage:

179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137859 isPrime

(an andere Leser: große Primzahlen sind wichtig in kryptographischen Algorithmen)

Kommentar von Machtnix53 ,

Einfacher vielleicht, aber viel langsamer, wenn du auch durch nicht-prime Zahlen teilst.

Kommentar von sarahj ,

richtig. es wird natürlich erst bei grossen Zahlen auffällig. Wenn man den 64bit Integer-Bereich verlässt, werden Divisionen von großen Zahlen sehr teuer.

Antwort
von winkler, 12

Keiner sollte hier antworten, um einen Lernenden das Lernen abzunehmen. Lehrer geben Übungsaufgaben, damit die "Schüler" dabei etwas lernen. Die Antwort-Kultur der "Antwortenden" sollte darauf Rücksicht nehmen, ob ein Entwickler ein "echtes" Problem hat, oder ein Schüler nur zu faul ist, seine Hausaufgaben zu machen.

Danke für die Beachtung aller Internet-Etikette

Keine passende Antwort gefunden?

Fragen Sie die Community