![\"naive](\"https:\/\/gigers.com\/blog\/wp-content\/uploads\/2021\/12\/Primzahlenbestimmung_Programm_naiv-1024x631.png\")
Dieser einfache Algorithmus funktioniert f\u00fcr Zahlen > 1 gut, ist aber sehr langsam, da viele unn\u00f6tigen Berechnungen durchgef\u00fchrt werden. Dies sieht man, wenn man alle Zahlen auff\u00fchrt, welche bei den Divisionen verwendet werden.<\/p>\n Es f\u00e4llt sofort auf, dass viele unn\u00f6tige Rechenschritte durchgef\u00fchrt werden, weil beispielsweise alle geraden Zahlen (ausser der 2) sicherlich keine Primzahlen sind. Trotzdem wird beispielsweise bei der 50 noch lange weitergerechnet, selbst wenn schon fr\u00fch klar ist, dass es sich nicht um eine Primzahl handeln kann.<\/p>\n Die Vermeidung unn\u00f6tiger Rechenschritte bedingt die Neuformulierung des Algorithmus. Daf\u00fcr muss die for-Schleife in Snap! durch eine while-Schleife ersetzt werden. Allerdings steht diese nicht standardm\u00e4ssig zu Verf\u00fcgung, weshalb diese zuerst programmiert werden muss. In Snap! funktioniert dies wie folgt:<\/p>\n Mit der durch die while-Schleife m\u00f6gliche Anpassung des Algorithmus werden unn\u00f6tige Rechenschritte verhindert.<\/p>\n Dies wird deutlich, wenn man sich noch einmal alle Zahlen anschaut, die nun in den notwendigen Divisionen verwendet werden.<\/p>\n Bei allen Zahlen, welche keine Primzahlen sind, wird die Berechnung schon sehr fr\u00fch abgebrochen. Dies ist auch deshalb von Interesse, weil Primzahlen seltener werden, wenn man gr\u00f6ssere Zahlen untersucht. Das wird bereits in der oben abgebildeten Grafik deutlich:<\/p>\n Um das Programm weiter zu optimieren, ist eine mathematische Betrachtung von Teilern notwendig.<\/p>\n Die Teiler einer bestimmten Zahl treten immer paarweise auf, wobei es vorkommen kann, dass die beiden Teiler gleich gross sind:<\/p>\n Zu jedem grossen Teiler geh\u00f6rt also ein entsprechend kleiner Teiler. Bei der Quadratzahl 25 ist gut ersichtlich, dass zum Teiler 5 kein Teiler vorhanden ist, der gr\u00f6sser als 5 ist, sonst m\u00fcsste es sich, z.B. bei 5 x 6 um eine gr\u00f6ssere Zahl handeln.<\/p>\n Damit ist es m\u00f6glich, die zu \u00fcberpr\u00fcfenden Teiler weiter einzuschr\u00e4nken. Statt bei Primzahlen bis zu n-1 zu pr\u00fcfen, reicht eine Pr\u00fcfung bis zur Quadratwurzel von n aus.<\/p>\n Die \u00c4nderung im Algorithmus beschr\u00e4nkt sich dabei auf das Abbruchkriterium in der while-Schleife.<\/p>\n Dadurch verringert sich der Rechenaufwand bei den bisher aufw\u00e4ndigen Primzahlen noch einmal dramatisch, was die Auflistung der ben\u00f6tigten Teiler zeigt:<\/p>\n Eine weitere Optimierung ist m\u00f6glich, indem man nicht mehr alle Zahlen als Teiler verwendet, sondern nur noch die Primzahlen selbst. Dabei stellt sich aber die Frage, woher dann diese Primzahlen im Voraus bekannt sein sollen.<\/p>\n Mit einem entsprechenden h\u00f6heren Aufwand beim Schreiben des Algorithmus ist es tats\u00e4chlich m\u00f6glich, die Primzahlen aus sich selbst heraus zu erzeugen. Als Voraussetzung wird dazu nur eine Liste mit dem Element 2 ben\u00f6tigt. Alle weitere Primzahlen kann das folgende Programm daraus generieren.<\/p>\n Nach dem ersten Durchlauf des Programms besteht die Liste aus den Zahlen 2 und 3, denn es wird bis maximal zur Zahl 3 gepr\u00fcft und diese ist nicht durch 2 teilbar.\u00a0Nach dem zweiten Durchlauf sind die Primzahlen 5 und 7 dazugekommen, denn das Programm pr\u00fcft nun bis 8.\u00a0Der n\u00e4chste Durchlauf pr\u00fcft bis 48 und liefert als letzte Primzahl 47 zur\u00fcck. Bei jedem weiteren Durchlauf wird der untersuchte Zahlenraum gr\u00f6sser und damit die Liste der Primzahlen l\u00e4nger. So k\u00f6nnen aus der 2 alle weiteren Primzahlen generiert werden.<\/p>\n Nebst der schnelleren Berechnung hat dieser Ansatz auch den Vorteil, dass die Berechnung der Primzahlen jederzeit angehalten und sp\u00e4ter wieder fortgesetzt werden kann. Denn alles, was das Programm daf\u00fcr ben\u00f6tigt, ist die Liste mit den Primzahlen, aus welcher es die gr\u00f6sste Primzahl ausliest, um weitere Berechnungen anzustellen.<\/p>\n Im gezeigten Beispiel darf der Computer dazu nicht ausgeschaltet werden, da sich die Liste im fl\u00fcchtigen Speicher befindet. Die gef\u00fchrte Liste k\u00f6nnte aber auch auf eine Harddisk geschrieben werden, wodurch das Programm seine Arbeit auch nach einem tats\u00e4chlichen Unterbruch wieder aufnehmen k\u00f6nnte.<\/p>\n Die Laufzeiten der unterschiedlichen Varianten unterscheiden sich dramatisch. Gemessen wurde jeweils die Zeit, welche zur Berechnung der ersten n Primzahlen notwendig war.<\/p>\n W\u00e4hrend bei der einfachsten Version die Laufzeiten immer st\u00e4rker zunehmen, verhalten sich diese in der optimierten Fassung zumindest im untersuchten Zahlenbereich fast linear. Diese Unterschiede sind bei kleinen Zahlenbereich noch klein, werden aber schnell immer gr\u00f6sser.<\/p>\n Die vorgestellten Ans\u00e4tze k\u00f6nnen nicht nur daf\u00fcr verwendet werden, bei gr\u00f6sseren Zahlen herauszufinden, ob es sich dabei um Primzahlen handelt. Sie bieten auch eine gute Gelegenheit daf\u00fcr, mit den Sch\u00fclerinnen und Sch\u00fclern die Notwendigkeit der Optimierung von Programmen zu besprechen.<\/p>\n Diese spielt bei vielen Computeranwendungen eine wichtige Rolle, nicht nur weil dadurch Energie und die damit verbundenen Kosten eingespart werden k\u00f6nnen, sondern dadurch werden auch Anwendungen m\u00f6glich, die vorher aus Zeitgr\u00fcnden nicht praktikabel umgesetzt werden konnten.<\/p>\n","protected":false},"excerpt":{"rendered":" Primzahlen bilden eine Grundlage der Mathematik und sind deshalb auch auf der Sekundarstufe I ein Thema. Allerdings beschr\u00e4nkt sich die Auseinandersetzung auf dieser Stufe h\u00e4ufig darauf, die Primzahlen mithilfe des Siebes von Eratosthenes zu gewinnen und diese anschliessend f\u00fcr die Primfaktorzerlegung von nat\u00fcrlichen Zahlen zu verwenden. Dabei bietet sich das Thema auf gut daf\u00fcr an, … <\/p>\n![\"\"](\"https:\/\/gigers.com\/blog\/wp-content\/uploads\/2021\/12\/Primzahlen_naiv_bis_50-1024x768.png\")
M\u00f6glichst fr\u00fchzeitiger Abbruch<\/h2>\n
![\"\"](\"https:\/\/gigers.com\/blog\/wp-content\/uploads\/2021\/12\/while-Schleife.png\")
![\"\"](\"https:\/\/gigers.com\/blog\/wp-content\/uploads\/2021\/12\/Primzahl_optimiert-1024x836.png\")
<\/p>\n![\"\"](\"https:\/\/gigers.com\/blog\/wp-content\/uploads\/2021\/12\/Primzahlen_optimiert_bis_50-1024x714.png\")
\n
Eigenschaften von Teilern<\/h2>\n
\n
![\"\"](\"https:\/\/gigers.com\/blog\/wp-content\/uploads\/2021\/12\/optimierte_while-Schleife-1024x201.png\")
<\/p>\n![\"\"](\"https:\/\/gigers.com\/blog\/wp-content\/uploads\/2021\/12\/Primzahlen_weiter_optimiert_bis_50-1024x138.png\")
Nimm 2<\/h2>\n
![\"\"](\"https:\/\/gigers.com\/blog\/wp-content\/uploads\/2021\/12\/Primzahlen_mit_Liste-918x1024.png\")
Laufzeiten<\/h2>\n
![\"\"](\"https:\/\/gigers.com\/blog\/wp-content\/uploads\/2021\/12\/Laufzeiten_Primzahlberechnung-1024x615.png\")
Anwendung im Unterricht<\/h2>\n