www.jb-electronics.de » Programmieren » Java » Primat
Der Primat heißt mit vollem Namen eigentlich Prim-O-Mat, wurde aber aufgrund des höheren Wiedererkennungswert dann doch Primat genannt. Dem aufmerksamen Leser mag schon aufgegangen sein, dass das Programm etwas mit Primzahlen zu tun hat. Richtig, Primat ist ein Programm, das kleine Ganzzahlen in ihre Primfaktoren zerlegen kann. Hier sind ein paar Beispielaufrufe zu sehen:
Das Programm besitzt einen Algorithmus, der feststellt ob eine Zahl n eine Primzahl ist. Das funktioniert so, indem in einer Schleife die Zahl n auf Teilbarkeit durch alle Zahlen von 2...Wurzel(n) getestet wird. Denn durch 1 teilbar ist eine Zahl immer. Aber warum bis Wurzel(n) und nicht bis n? Das liegt daran, dass Primfaktoren nicht aus Quadratur entstanden sein können, da sie nur ein ganzzahliges Vielfaches von 1 mit sich selbst sind. Insofern stellt dieser Ansatz bereits eine Optimierung dar. Natürlich kann der Algorithmus weiter optimiert werden, aber darum sollte es hier ironischerweise nicht primär gehen.
Anmerkung: Die Wurzelfunktion ist im Quellcode ebenfalls selbst rekursiv programmiert; das sogenannte Heron-Verfahren wird benutzt, bei dem das Konvergenzverhalten einer rekursiven Folge ausgenutzt wird. Doch darum soll es hier eigentlich nicht gehen.
Um nun die Primfaktorzerlegung zu erhalten, wird dieser Primzahltest rekursiv aufgerufen: wenn eine Zahl n durch m teilbar ist (das heißt dass die Restdividion oder auch Modulodivision von n durch m null ergibt), wird m zur Liste der Primfaktoren hinzugefügt, und danach wird n / m dem gleichen Test rekursiv unterzogen (da n / m wieder eine Ganzzahl ist, da m ja nach Voraussetzung ein Teiler von n ist).
Wer sich das Programm anschauen möchte, der kann es hier herunterladen: Primat.zip (27 KB).
www.jb-electronics.de » Programming » Java » Primat
There is no English translation of this page available yet. It will take some more time for me to translate the whole website.
If you have a particular interest in this page getting translated as fast as possible, please contact me; I will see what I can do. Please click here for the German version.