Primzahlen sind Zahlen, die nur durch sich selbst und durch eins geteilt werden, ohne andere Teiler zu haben. Sie spielen eine wichtige Rolle in Mathematik und Kryptographie. Das Finden von Primzahlen ist eine der Hauptaufgaben in Mathematik und Informatik. In diesem Artikel werden wir die grundlegenden Methoden und Algorithmen für die Suche nach Primzahlen untersuchen.
Eine der einfachsten Möglichkeiten, Primzahlen zu finden, besteht darin, alle Zahlen von 2 bis zur zu überprüfenden Zahl zu durchlaufen und ihre Teilbarkeit zu überprüfen. Diese Methode wird als iterative Methode bezeichnet. Es ist einfach zu implementieren, aber für große Zahlen ineffizient, da es eine Überprüfung jeder Zahl erfordert.
Eine effizientere Methode, um Primzahlen zu finden, ist ein eratosthenes Sieb. Es basiert auf dem Prinzip, alle Vielfachen Zahlen aus der Liste der Zahlen zu entfernen. Zuerst wird eine Liste aller Zahlen von 2 bis zum angegebenen Limit erstellt. Dann werden nacheinander alle Vielfachen von Zahlen entfernt, beginnend mit 2. Nach Abschluss des Vorgangs werden nur Primzahlen in der Liste angezeigt.
Ein weiterer effektiver Algorithmus zur Suche nach Primzahlen ist der Miller-Rabin-Test. Es basiert auf der probabilistischen Überprüfung einer Zahl auf Einfachheit. Der Algorithmus überprüft die Zahl wiederholt anhand von Zufallszahlen auf Einfachheit und iteriert, um die Genauigkeit der Überprüfung zu erhöhen. Dieser Ansatz ermöglicht es Ihnen, die Einfachheit großer Zahlen effektiv zu bestimmen.
Methode zum Durchbrechen von Teilern
Der Algorithmus der Teiler-Iterationsmethode kann wie folgt dargestellt werden:
| 1 | Wir legen die Zahl fest, bis zu der wir nach Primzahlen suchen werden. |
| 2 | Wir durchlaufen alle Zahlen von 2 bis zu einer bestimmten Zahl. |
| 3 | Überprüfen Sie, ob die angegebene Zahl ohne Rest durch die aktuelle Zahl geteilt wird. |
| 4 | Wenn geteilt, ist die Zahl keine Primzahl. |
| 5 | Wenn alle Zahlen von 2 bis zu einer bestimmten Zahl sie nicht restlos teilen, ist die Zahl eine Primzahl. |
Der Vorteil der Methode zum Sortieren der Teiler liegt in ihrer Einfachheit und Verständlichkeit. Es ist jedoch ineffizient, insbesondere bei der Arbeit mit großen Zahlen, da es erfordert, dass alle Zahlen von 2 bis zu einer bestimmten Zahl durchlaufen werden.
In der Praxis wird diese Methode aufgrund ihrer geringen Arbeitsgeschwindigkeit selten verwendet. Stattdessen ist es vorzuziehen, komplexere, aber effizientere Algorithmen wie den Eratosthenalgorithmus oder den Miller-Rabin-Test zu verwenden.
Primzahlen finden, indem alle möglichen Teiler überprüft werden
Für jede Zahl $x$ aus dem Intervall $[2, \sqrt]$, überprüfen Sie, ob $n$ ohne Rest durch $x$ geteilt wird. Wenn geteilt, ist die Zahl $n$ ein zusammengesetzter Wert und wir beenden die Überprüfung. Andernfalls ist die Zahl $n$ eine Primzahl.
Diese Methode ist einfach zu implementieren, aber ihr Hauptnachteil ist die hohe Rechenkomplexität für große Zahlen. Bei der Suche nach sehr großen Primzahlen sollten effizientere Algorithmen verwendet werden, z. B. Algorithmen zur Überprüfung von Zahlen auf Einfachheit basierend auf dem Eratosthengitter oder Einfachheitstests wie dem Miller-Rabin-Test oder dem Farm-Test.
Bei kleinen Werten von $n$ kann die Methode zur Überprüfung aller möglichen Teiler jedoch effizient und benutzerfreundlich genug sein.
Eratosthen-Siebmethode
Für die Verwendung der Eratosthen-Siebmethode ist es notwendig:
- Erstellen Sie eine Liste aller Zahlen im angegebenen Bereich. Die Anfangsliste enthält alle Zahlen von 2 bis N, wobei N die obere Grenze ist.
- Beginnend mit der ersten Zahl in der Liste (2) werden alle Vielfachen der Zahl aus der Liste gestrichen.
- Springt zur nächsten ungeraden Zahl, die nicht durchgestrichen ist, und wiederholt den Vorgang.
- Wiederholen Sie die Schritte 2 und 3, bis alle Zahlen in der Liste angezeigt werden.
Als Ergebnis der Ausführung des Algorithmus bleiben nur Primzahlen in der Liste übrig.
Die Eratosthene-Siebmethode ist eine der schnellsten und effektivsten Möglichkeiten, Primzahlen zu finden. Es ermöglicht Ihnen, viele schwierige Zahlen schnell auszusortieren und nur Primzahlen zu finden, was es besonders nützlich macht, wenn Sie mit großen Zahlen und großen Bereichen arbeiten.
Primzahlen mit einem Eratostherstellergitter finden
Die Idee eines Eratosthenes-Gitters besteht darin, alle Zahlen, die ein Vielfaches der aktuellen Primzahl sind, konsequent auszuschließen. Zuerst wird eine Liste von Zahlen von 2 bis N erstellt, wobei N die Zahl ist, bis zu der wir Primzahlen finden wollen.
Wählen Sie dann die erste unmarkierte Zahl aus der Liste (2) aus und durchstreichen Sie alle Vielfache davon (4, 6, 8 usw.). Wählen Sie dann die nächste unmarkierte Zahl (3) aus und wiederholen Sie den Vorgang, indem Sie alle Vielfachen durchgestrichen werden.
Wir setzen diesen Prozess fort, bis wir das Ende der Liste erreicht haben. Als Ergebnis bleiben nur nicht markierte Zahlen übrig, bei denen es sich um Primzahlen handelt.
Mit dem Eratosthenisier können Sie schnell alle Primzahlen bis zu einer bestimmten Zahl N finden. Dieser Algorithmus hat eine Komplexität von O(N*log(log(N))), was ihn besonders nützlich macht, wenn er mit großen Zahlen arbeitet.
Testteilungs-Methode
Die Anwendung der Testteilungs-Methode impliziert eine sequenzielle Überprüfung der Zahl n durch die Teilbarkeit durch alle Zahlen von 2 bis √n. Wenn keine dieser Zahlen ein Zahlenteiler ist n, dann wird die Zahl als Primzahl betrachtet.
Bei der Implementierung der Testteilungs-Methode können Sie Optimierungen verwenden, z. B. nur ungerade Zahlen überprüfen oder bereits gefundene Primzahlen als Teiler verwenden. Das Wesen der Methode bleibt jedoch unverändert.
Lassen Sie uns feststellen, ob die Zahl 17 eine Primzahl ist. In diesem Fall prüfen wir, ob die Zahl 17 durch Zahlen von 2 bis √17 ≈ 4,12. Nach den durchgeführten Prüfungen stellen wir sicher, dass die Zahl 17 nicht mit einer dieser Zahlen geteilt wird, was bedeutet, dass sie einfach ist.
Verwenden der Testteilung, um die Einfachheit einer Zahl zu bestimmen
Um die Einfachheit der Zahl N anhand einer Test Division zu bestimmen, müssen Sie die Teilbarkeit der Zahl N durch alle Zahlen im Bereich von 2 bis zur Wurzel von N nacheinander überprüfen. Wenn die Zahl N ohne Rest durch eine dieser Zahlen geteilt wird, ist sie keine Primzahl. Wenn die Zahl N jedoch nicht durch eine dieser Zahlen geteilt wird, ist sie mit hoher Wahrscheinlichkeit eine Primzahl.
Der Vorteil der Testteilung ist seine Einfachheit und relative Arbeitsgeschwindigkeit. Da wir die Teilbarkeit einer Zahl nur durch Zahlen in einem relativ kleinen Bereich überprüfen, ist diese Methode geeignet, um die Einfachheit von Zahlen in einem großen Bereich schnell zu überprüfen.
Der Nachteil der Verwendung der Testteilung ist jedoch die hohe Arbeitsintensität für große Zahlen. Wenn wir die Einfachheit einer großen Zahl von N überprüfen, müssen wir alle Zahlen im Bereich von 2 bis zur Wurzel von N dividieren, was eine beträchtliche Zeit in Anspruch nehmen kann.
Miller-Rabin-Testmethode
Die Grundidee der Methode ist wie folgt:
- Eine Zufallszahl wird ausgewählt a aus dem Intervall [2, n - 2], wo n - eine Zahl, die auf Einfachheit überprüft wird.
- Die Reste der Division einer Zahl werden berechnet a auf zwei Grad.
- Wenn einer der Reste 1 oder -1 ist (mod n), dann die Zahl n kann einfach sein. In diesem Fall wird die Überprüfung mit der folgenden Zufallszahl fortgesetzt a.
- Wenn alle Reste nicht gleich 1 oder -1 sind (mod n), dann die Zahl n zusammengesetzt.
- Wiederholen Sie die Schritte 1 bis 4 mehrmals, um die Genauigkeit des Ergebnisses zu erhöhen.
Die Miller-Rabin-Testmethode hat eine hohe Wahrscheinlichkeit, die Einfachheit einer Zahl zu bestimmen. Es kann verwendet werden, um Zahlen mit sehr vielen Ziffern zu überprüfen und ist eine der grundlegenden Methoden zur ungefähren Suche nach Primzahlen.
Miller-Rabin-Algorithmus zur Überprüfung der Einfachheit einer Zahl
Der Miller-Rabin-Algorithmus funktioniert wie folgt:
- Die Basis a wird ausgewählt, die kleiner als die zu überprüfende Zahl n sein muss.
- Die Zahl n-1 wird in die Potenz von zwei und eine ungerade Zahl zerlegt, dh n-1 = 2 ^ r * s, wobei s ungerade ist.
- Es werden aufeinanderfolgende Werte von a^s mod n, (a^2s mod n), berechnet. (a^(2^r * s) mod n).
- Wenn für mindestens einen Wert von a^((2^i)*s) mod n das Ergebnis nicht 1 ist und für alle i von 0 bis r-1 nicht n-1 ist, wird die Zahl n als zusammengesetzt betrachtet, und die Iteration des Algorithmus wird beendet.
- Wenn alle Werte 1 oder n-1 sind, ist die Zahl n wahrscheinlich einfach, der Algorithmus iteriert weiter mit der neuen Basis a oder wird beendet, wenn das Wiederholungslimit erreicht ist.
Als Ergebnis des Algorithmus können Sie zwei Ergebnisse erhalten: Die Zahl n ist wahrscheinlich eine Primzahl oder die Zahl n ist wahrscheinlich eine zusammengesetzte Zahl. Je mehr Iterationen durchgeführt werden und einfache Ergebnisse erhalten werden, desto höher ist die Wahrscheinlichkeit, dass die Zahl tatsächlich eine Primzahl ist.
Der Miller-Rabin-Algorithmus wird in verschiedenen Softwaresystemen und -anwendungen verwendet, um die Einfachheit großer Zahlen zu testen, z. B. in der Kryptographie oder beim Generieren von Primzahlen zur Verschlüsselung.
