Prüfen ob eine Zahl prim ist und alle Primzahlen in einem Bereich finden
Eine Primzahl ist eine natürliche Zahl größer als 1, die keine positiven Teiler außer 1 und sich selbst hat. 2, 3, 5, 7, 11, 13... sind die ersten Primzahlen. Der Fundamentalsatz der Arithmetik besagt, dass jede ganze Zahl größer als 1 eindeutig als Produkt von Primzahlen ausgedrückt werden kann.
Dieses Tool prüft, ob eine Zahl prim ist, findet ihre Primfaktorzerlegung und listet Primzahlen in einem gegebenen Bereich. Primzahlen bilden die Grundlage der modernen Kryptografie — RSA basiert auf der Schwierigkeit, große Zahlen in ihre Primfaktoren zu zerlegen.
Für kleine Zahlen (<10⁶): Probedivision bis √n. Für mittlere Zahlen: deterministischer Miller-Rabin. Für sehr große Zahlen: probabilistischer Miller-Rabin. AKS (2002) wurde als polynomiell-zeitig bewiesen.
Ja. Euklid bewies dies um 300 v.Chr.: Nimm eine endliche Liste von Primzahlen, multipliziere sie alle und addiere 1 — dieser Wert ist prim oder durch eine nicht gelistete Primzahl teilbar. Widerspruch.
Algorithmus zum Finden aller Primzahlen bis zu einem Limit n. Markiert alle Vielfachen jeder Primzahl als nicht prim. Verbleibende unmarkierte Zahlen sind prim. Zeitkomplexität: O(n log log n).
Eine Mersenne-Primzahl ist eine Primzahl der Form 2ⁿ − 1. Beispiele: 3, 7, 31, 127. GIMPS koordiniert verteiltes Rechnen zum Finden neuer Mersenne-Primzahlen.
Prozentrechner · Altersrechner · Datumsdifferenz · Wissenschaftlicher Rechner · BMI-Rechner · Fibonacci-Generator