TI-Basic: Programme und Tutorials: Unendlich viele Primzahlen berechnen
| Erstellt von: | Peter Riedel |
| Schwierigkeitsgrad: | fortgeschritten |
| Modell: | Voyage 200 |
Unendlich viele Primzahlen berechnen
BearbeitenFolgendes Programm berechnet theoretisch unendlich viele Primzahlen. In der Praxis wird die Rechenleistug inbesondere durch den Prozessor und RAM begrenzt. Außerdem werden TI-Basic-Programme deutlich langsamer ausgeführt als Programme hardwarenaher Programmiersprachen wie z.B. C und Assembler. Daher stößt der Taschenrechner bei diesem Programm relativ schnell an seine Grenzen. Innerhalb weniger Minuten werden einige Hundert Primzahlen berechnet und ausgegeben. Zum Vergleich: Dasselbe Programm in C hat nach etwas mehr als einer Minute bereits rund 20 Millionen Zahlen auf die Eigenschaft einer Primzahl überprüft und die Primzahlen ausgegeben.
Erklärung
Bearbeitenn ist eine natürliche Zahl, die auf die Eigenschaften einer Primzahl überprüft wird. t ist der natürliche Teiler. i ist ein Schalter, der entscheidet, ob n um zwei oder vier erhöht wird. w enthält die Wurzel aus n.
Primzahlen haben die Eigenschaft, dass sie bei der Division durch ganze Zahlen, nur dann keinen Rest hinterlassen, wenn man sie durch sich selbst oder eins teilt. Voraussetzung sind also genau zwei natürliche Teiler. Um Zahlen zu filtern, die keine Primzahlen sind, gilt es also einen dritten natürlichen Teiler zwischen eins und √(n) zu finden. Wenn der natürliche Teiler t soweit erhöht wurde, dass er größer oder gleich √(n) ist, ohne dass bis dahin ein dritter natürlicher Teiler ohne Rest gefunden wurde, dann wird kein weiterer Teiler mehr danach auftauchen und es handelt sich daher um eine Primzahl. Der Rechenprozess kann also an dieser Stelle unterbrochen werden. Wenn zuvor ein dritter Teiler gefunden wurde, wird die Berechnung sofort abgebrochen. Die zu untersuchenden Zahlen sind ungerade, da alle geraden Zahlen ein Vielfaches von Zwei und daher restlos teilbar durch zwei sind, was sie wiederum nicht zu Primzahlen macht und daher eine Überprüfung überflüssig ist. Stattdessen werden nur Zahlen betrachtet, die auf 1, 3, 5, 7 oder 9 enden und abwechselnd um 2 oder 4 bei 5 beginnend erhöht werden. Da ungerade Zahlen niemals restlos durch gerade Zahlen geteilt werden können, gilt dasselbe für die natürlichen Teiler: Sie sind ungerade, enden auf 1, 3, 5, 7, 9 und werden in Zweierschritten beginnend ab 3 erhöht. Diese Optimierung dient dem Zweck die Rechenleistung zu maximieren.
In der äußeren Endlosschleife wird zunächst die Wurzel von n als oberer Grenzwert berechnet, ab der die Berechnung spätestens nicht weitergeführt werden soll. Am Ende dieser Schleife befindet sich der Schalter, der entscheidet um wieviel n erhöht wird. Darüberhinaus wird t für die nächste Berechnung zurückgesetzt. In der inneren Schleife ist der konkrete Algorithmus zur Überprüfung der Primzahleigenschaften implementiert. Mithilfe der mod(n,t)-Funktion wird der Rest berechnet und falls ein dritter restloser Teiler existiert die Schleife ohne Ausgabe abgebrochen. Falls nicht, wird überprüft ob der Teiler t bereits größer oder gleich √(n) ist. Trifft dies zu, handelt es sich um eine Primzahl, da bis dort kein dritter restloser Teiler aufgetaucht ist, woraufhin die Primzahl ausgegeben und die innere Endlosschleife abgebrochen wird. Der neue Wert von n und der Startwert von t werden für die neue Berechnung dann in der äußeren Endlosschleife gesetzt und das Ganze beginnt von vorn.
Man kann natürlich auch für n andere Startwerte setzen, muss den Schalter aber entsprechend anpassen. Die äußere Loop-Schleife lässt sich auch mit einer While-Schleife ersetzen, die überprüft ob n die Obergrenze überschritten hat oder nicht, falls man nur eine bestimmte Menge von Zahlen auf Primzahleigenschaften prüfen möchte.
Programm
Bearbeiten:prime() :Prgm :ClrIO :0->i :5->n :3->t :Loop : √(n)->w : Loop : If mod(n,t)=0 Then : Exit : ElseIf w≤t Then : Disp n : Exit : EndIf : t+2->t : EndLoop : If i=0 Then : n+2->n : 1->i : Else : n+4->n : 0->i : EndIf : 3->t :EndLoop :EndPrgm