Inhalt
So arbeitet der Rechner für die nächste Primzahl
Tragen Sie eine nichtnegative ganze Zahl n ein. Der Rechner sucht die erste Primzahl p mit p > n und nennt zusätzlich den Abstand sowie die Zahl der tatsächlich geprüften ungeraden Kandidaten.
Die strenge Grenze entscheidet
„Nächste“ bedeutet hier immer strikt größer. Eine bereits eingegebene Primzahl bleibt deshalb nicht stehen: aus 17 wird 19. Gesucht wird auch nicht die Primzahl mit dem kleinsten Abstand in beide Richtungen.
Die Menge ℙ enthält die Primzahlen. Der Rechner beginnt bei n + 1. Liegt n unter 2, wird 2 als erster möglicher Wert behandelt. Danach genügt es, ungerade Zahlen zu prüfen.
Für einen Kandidaten werden mögliche Teiler nur bis zur Quadratwurzel gesucht. Hat eine zusammengesetzte Zahl zwei Faktoren, muss mindestens einer davon höchstens so groß wie ihre Quadratwurzel sein. Bleibt dieser Bereich ohne Treffer, ist der Kandidat prim.
- Startwert übernehmen und um eins erhöhen.
- Gerade Zahlen oberhalb von 2 überspringen.
- Ungerade Kandidaten vollständig prüfen und beim ersten Primzahlfund anhalten.
Drei typische Suchwege
n = 1: Das Ergebnis ist 2, der Abstand beträgt 1. Genau ein Kandidat wird gezählt. Damit bleibt die Sonderstellung der 1 korrekt erhalten.
n = 29: Die 30 wird als gerade Zahl übersprungen, anschließend ist 31 prim. Der Abstand beträgt 2, geprüft wird nur ein ungerader Kandidat.
n = 1000: Geprüft werden 1001, 1003, 1005, 1007 und 1009. Erst 1009 ist prim. Damit lauten die Zusatzwerte 9 für den Abstand und 5 für die Kandidaten.
Ein kurzer Abstand sagt nichts über die Größe der Eingabe aus. Nach 100 folgt sofort 101, während schon nach 14 zunächst die zusammengesetzte 15 ausscheidet und erst 17 passt.
Was die Zusatzangaben nicht bedeuten
Die Zahl der Kandidaten ist kein Laufzeitmesser. Sie zählt geprüfte ungerade Zahlen, nicht einzelne Divisionen.
Eine zusammengesetzte Zahl kann bereits am Teiler 3 scheitern. Bei einer Primzahl muss die Suche dagegen bis zur vollständigen Grenze laufen. Zwei Aufgaben mit gleich vielen Kandidaten können daher unterschiedlich viele Rechenschritte benötigen.
Zulässig sind ganze Zahlen von 0 bis 1.000.000.000.000. Am oberen Rand ergibt sich 1.000.000.000.039. Dieser Wert liegt über der Eingabegrenze, ist aber weiterhin exakt darstellbar. Dezimalzahlen, negative Werte und leere Eingaben werden abgewiesen.
Häufige Fragen zur nächsten Primzahl
Die Antworten helfen vor allem dabei, „nächste“, „nächstgelegene“ und „geprüft“ auseinanderzuhalten.
Wird eine eingegebene Primzahl zurückgegeben?
Nein. Gesucht wird strikt oberhalb von n. Bei n = 17 lautet das Ergebnis deshalb 19.
Warum ist 2 das Ergebnis für 0 und 1?
Die 2 ist die kleinste Primzahl und größer als beide Eingaben. Weder 0 noch 1 ist eine Primzahl.
Zählt eine übersprungene gerade Zahl als Kandidat?
Nein. Gerade Zahlen über 2 sind sicher zusammengesetzt und werden vor der eigentlichen Primzahlprüfung entfernt.
Kann die gefundene Zahl über der Eingabegrenze liegen?
Ja. Die Grenze gilt für n. Für 1.000.000.000.000 wird exakt die Primzahl 1.000.000.000.039 gefunden.
Ist das Verfahren probabilistisch?
Nein. Jeder Kandidat wird durch Teilbarkeit bis zur Quadratwurzel exakt geprüft.
Existiert nach jeder ganzen Zahl eine weitere Primzahl?
Ja. Es gibt unendlich viele Primzahlen. Der Rechner beschränkt nur die erlaubte Eingabe und den exakt darstellbaren Zahlenbereich.
Ähnliche Rechner
Die folgenden Rechner zum gleichen Thema könnten für Sie nützlich sein:
- Z-Wert-Rechner. Bestimmen Sie die relative Lage eines Messwerts oder rechnen Sie einen Z-Wert auf die ursprüngliche Skala zurück.
- kgV-Rechner. Geben Sie zwei ganze Zahlen mit jeweils bis zu 100 Ziffern ein und erhalten Sie das exakte kgV.
- ggT-Rechner. Geben Sie zwei ganze Zahlen mit jeweils bis zu 100 Ziffern ein und erhalten Sie den exakten ggT.
- Ziffernwurzel-Rechner. Geben Sie eine ganze Zahl mit bis zu 10.000 Ziffern ein und verfolgen Sie die Reduktion auf eine Ziffer.
- Kombinationen berechnen. Geben Sie Gesamtzahl und Auswahlgröße ein, um die genaue Anzahl möglicher Gruppen zu erhalten.
- Rechner für Division mit Rest. Geben Sie einen ganzzahligen Dividenden und einen Divisor ungleich null ein, um Quotient und Rest zu berechnen.
- Grad in Radiant umrechnen. Gib einen Winkel in Grad oder Radiant ein und lies den entsprechenden Wert sofort ab.
- Primzahl prüfen. Geben Sie eine ganze Zahl ein, um sie als prim, zusammengesetzt oder Sonderfall einzuordnen.
- Superfakultät-Rechner. Geben Sie ein ganzes n ein, um alle Fakultäten von 1! bis n! zu multiplizieren.
- Primfakultät-Rechner. Geben Sie eine ganzzahlige Obergrenze ein, um alle Primzahlen bis n zu multiplizieren.
In sozialen Medien teilen
Wenn es Ihnen gefallen hat, teilen Sie bitte den Rechner auf Ihren sozialen Medien. Es ist einfach für Sie und nützlich für die Promotion des Projekts. Danke!