Primzahlen berechnen

Elektronik-Labor Projekte Mikrocontroller Pico Basic

Kürzlich habe ich mal auf einem VC20 versucht, ein Basic-Programm zur Berechnung von Primzahlen zu schreiben. Ich konnte mich erinnern, dass ich sowas auf meinem Sharp-Taschenrechner locker hinbekommen hatte. Aber das ist lange her, und diesmal habe ich es nicht fehlerfrei geschafft. Das hat mich gewurmt. Und deshalb habe ich mich gefragt, ob ich es wenigstens in meinem PicoBasic schaffe.

Im ersten Versuch habe ich das Datenarray mit einer Zahlenfolge 0 bis 255 vollgeschrieben. Dann wurden in zwei Schleifen alle Zahlen multipliziert und die Produkte als Adresspointer verwendet, um auf diese Nicht-Primzahlen Nullen als Markierung zu schreiben. Die ganze Sache war aber problematisch, weil ich mit Bytes rechnen musste. Wenn ein Produkt zu groß wurde, konnte der Übertrag eine echte Primzahl löschen. Ich habe hin und her probiert, konnte aber keine Lösung für alle Primzahlen bis 100 finden.

Dann ist mir ein anderes Verfahren eingefallen. Um eine Zahl A zu testen, teile ich sie durch B und multipliziere das Ergebnis wieder mit B. Wenn das Ergebnis genau der Zahl A entspricht, war A keine Primzahl. Beispiel: A sei 9. Ich rechne 9/2=4,5, als Ganzzahl 4, dann 4*2=8, die 9 bekommt noch eine zweite Chance: 9/3=3 und 3*3=9, durchgefallen! Weil A und B auch noch für Vergleiche gebraucht werden, müssen sie in D und C zwischengespeichert werden. Die 2 würde übrigens nicht getestet und stattdessen am Anfang direkt mit Print ausgegeben, weil sie bei den Vergleichen Probleme hatte.

              REM Primzahl
              L5:
0x1A01 Delay s = 1
0x0102 A = 2
0x4200 Print A
0x0103 A = 3
0x3800 D = A
0x0202 B = 2
              L1:
0x3500 A = B
0x3600 C = A
0x3900 A = D
0x2D00 A = A / B
0x2C00 A = A * B
0x3400 B = A
0x3900 A = D
0x221A If A=B Goto L3:
0x3700 A = C
0x2800 A = A + 1
0x3400 B = A
0x3900 A = D
0x2218 If A=B Goto L2:
0x2006 Goto L1:
0x3700 A = C
0x2800 A = A + 1
0x3400 B = A
0x2006 Goto L1:
              L2:
0x1A01 Delay s = 1
0x4200 Print A
              L3:
0x3900 A = D
0x2800 A = A + 1
0x3800 D = A
0x02FF B = 255
0x2200 If A=B Goto L5:
0x0202 B = 2
0x2006 Goto L1:

Die Vergleiche steuern den Programmablauf: Wenn das Ergebnis der Multiplikation gleich der Testzahl ist, ist sie durchgefallen, und es geht weiter bei L3, wo A um 1 erhöht wird, um die nächste Zahl zu testen. Wenn B so groß wird wie A, wurde offensichtlich kein Teiler gefunden, also eine Primzahl erkannt und bei L2 mit Print ausgegeben. Und wenn A bis 255 gekommen ist, ist die gesamte Suche abgeschlossen und beginnt von vorn bei L5. Dass L5 ganz vorn steht, liegt daran, dass ich alles zuerst mit End abgeschlossen hatte und dann nachträglich doch lieber an den Anfang gesprungen bin.

Die Ausgaben im Bereich 0...255 passen gut zum Plotter im Testlabor. Damit hat man eine einfache Möglichkeit die Verteilung der Primzahlen zu betrachten. Ganz untern sind sie offensichtlich etwas häufiger, denn da verläuft die Kurve flacher. Aber dann sieht es im Bereich bis 255 fast nach einer Gleichverteilung aus. Nur knapp über 100 und dann wieder über 190 liegen einige Primzahlen dichter beieinander.

Fazit: Ich bin zufrieden, dass ich die Aufgabe doch noch lösen konnte, und dann auch noch mit PicoBasic. Allerdings wäre das Verfahren in einem vollen Basic mit mehr Variablen noch eleganter zu verwenden.

Download: Primzahl.pbas

Elektronik-Labor Projekte Mikrocontroller PicoBasic