Zu beweisen, dass eine Million prim ist, braucht tausend Divisionen, nicht eine Million
Veröffentlicht am 16.11.2026 · 3 Min. Lesezeit · Alltags-Rechner
Lena Hoffmann — Redakteurin Wissenschaft & Bildung bei OneKitly
Mathematik · Physik
Anhand von 2 Quellen geprüft
Um zu prüfen, ob eine Zahl einen Teiler hat, muss man nie über ihre Quadratwurzel hinausschauen. Zerfällt eine Zahl in zwei Faktoren, liegt einer bei oder unter der Wurzel und der andere bei oder über ihr — nichts Kleines zu finden heißt also, dass es gar nichts gibt. 1 000 003 zu prüfen verlangt daher Probedivisionen nur bis 1000, und sie übersteht jede: Sie ist prim. Ihre Nachbarin 1 000 001 fällt schnell, denn 101 teilt sie genau und lässt 9901 übrig. Die Quadratwurzel verwandelt eine unmögliche Suche in die Arbeit eines Nachmittags, und sie ist das Erste, was jede entdeckt, die einen Primzahltest schreibt.
1 000 003 ist prim, und der Beweis endet bei 1000, seiner Quadratwurzel. 1 000 001 ist es nicht, und die Suche endet beim dritten Versuch: 101 teilt es.
Nur die Primzahlen muss man versuchen
Durch 4 zu teilen ist vergebene Mühe, wenn 2 schon scheiterte — die Kandidatenliste sind nicht die tausend Zahlen unter der Wurzel, sondern die 168 Primzahlen darunter. Das allein sechstelt die Arbeit, und gerade Zahlen sowie Dreierviefache zu überspringen erledigt den Rest fast umsonst. Die klassische Implementierung prüft 2, dann 3, dann jede Zahl der Form „eins neben einem Vielfachen von sechs“, was jede mögliche Primzahl abdeckt und nur ein Drittel der ganzen Zahlen testet.
Warum der Kniff aufhört zu helfen
Die Stellenzahl zu halbieren klingt nach viel, bis die Zahl lang ist. Die Quadratwurzel einer 600-stelligen Zahl hat noch 300 Stellen; Probedivision an den Schlüsseln moderner Kryptografie bräuchte mehr Operationen, als es Atome im beobachtbaren Universum gibt. Echte Primzahltests geben die Division daher ganz auf und nutzen probabilistische Verfahren, deren Irrtumswahrscheinlichkeit unter jede genannte Schranke gedrückt werden kann. Diese Tests beweisen weit leichter, dass eine Zahl zusammengesetzt ist, als sie einen Faktor vorzeigen — genau die Asymmetrie, auf der die Sicherheit ruht.
| Zahl | Zu prüfende Divisionen | Ergebnis |
|---|---|---|
| 1 000 001 | 3 bis zum Scheitern | 101 × 9901 |
| 1 000 003 | 168 Primzahlen bis 1000 | Prim |
| Eine 600-stellige Zahl | Mehr als Atome im Universum | Unbrauchbar |
Häufige Fragen
- Warum ist 1 keine Primzahl?
- Per Entscheidung, damit die Faktorisierung eindeutig bleibt. Zählte 1 mit, ließe sich 12 als 2×2×3, als 1×2×2×3 oder als 1×1×2×2×3 schreiben, und der Satz, dass jede Zahl genau eine Primfaktorzerlegung hat, bräuchte eine Ausnahmeklausel. Tabellen des 19. Jahrhunderts führten 1 durchaus als Primzahl, und die Konvention wechselte, weil jeder Satz ohne sie sauberer wurde. Definitionen in der Mathematik werden wegen ihrer Folgen gewählt und nicht entdeckt — das ist das klarste kleine Beispiel dafür.
- Wie prüfe ich eine Zahl von Hand?
- Ziehen Sie die Wurzel, runden Sie auf und teilen Sie durch jede Primzahl bis dahin. Unter zehntausend sind das höchstens 25 Divisionen, von denen die meisten sofort erledigt sind: Gerade Zahlen scheitern an 2, durch drei teilbare Quersummen an 3, alles auf 0 oder 5 Endende an 5. Was zum ernsthaften Prüfen übrig bleibt, ist eine kurze Liste. Oberhalb einer Million wird die Methode mühsam statt schwierig — genau der Moment, sie einer Maschine zu übergeben.
Artikel, die dich interessieren könnten
Alle Ratgeber →Ähnliche Tools
Quellen
Hast du einen Fehler in diesem Artikel entdeckt?