Mathematik

Primzahl-Prüfer (bis 10.000.000)

Prüft sofort, ob eine ganze Zahl N (bis 10.000.000) eine Primzahl ist. Zeigt Probedivisions-Schritte, vorherige und nächste Primzahl sowie die Primfaktorzerlegung.

Die ersten 100 Primzahlen

#1–10 #2–11 #3–12 #4–13 #5–14 #6–15 #7–16 #8–17 #9–18 #10–19
2 3 5 7 11 13 17 19 23 29
31 37 41 43 47 53 59 61 67 71
73 79 83 89 97 101 103 107 109 113
127 131 137 139 149 151 157 163 167 173
179 181 191 193 197 199 211 223 227 229
233 239 241 251 257 263 269 271 277 281
283 293 307 311 313 317 331 337 347 349
353 359 367 373 379 383 389 397 401 409
419 421 431 433 439 443 449 457 461 463
467 479 487 491 499 503 509 521 523 541

Tipps

  • Eine Primzahl ist eine ganze Zahl größer als 1, die keine anderen Teiler als 1 und sich selbst hat. Die Folge beginnt mit 2, 3, 5, 7, 11, 13, …
  • Der einfachste Primzahltest ist die Probedivision: Dividiere N durch jede ganze Zahl von 2 bis √N. Wenn keine davon N teilt, ist N eine Primzahl.
  • 1 ist keine Primzahl. Die Definition verlangt "größer als 1". Die Zahl 2 ist die einzige gerade Primzahl.
  • Es gibt unendlich viele Primzahlen (bewiesen von Euklid um 300 v. Chr.). Ihre Dichte nimmt mit der Größe ab — in der Nähe von n ist etwa 1 von ln(n) ganzen Zahlen eine Primzahl (Primzahlsatz).

Häufige Fragen

2 hat keine anderen Teiler als 1 und sich selbst und ist daher per Definition eine Primzahl. Sie ist auch die einzige gerade Primzahl — jede andere gerade Zahl ist durch 2 teilbar.

Die Definition der Primzahl schließt 1 aus ("eine ganze Zahl größer als 1"). 1 auszuschließen ist notwendig, damit der Fundamentalsatz der Arithmetik gilt: Wäre 1 eine Primzahl, wären Faktorisierungen nicht eindeutig (z. B. 6 = 2 × 3 = 1 × 2 × 3).

Die Probedivision hat eine Zeitkomplexität von O(√N). Für N = 10.000.000 gilt √N ≈ 3162, sodass höchstens ~3162 Divisionen benötigt werden. Das ist für die interaktive Nutzung schnell genug.
ツールくん

Übrigens – Warum Primzahlen so wichtig sind

Primzahlen sind die "Atome der Arithmetik". Der Fundamentalsatz der Arithmetik besagt, dass jede ganze Zahl größer als 1 eine eindeutige Primfaktorzerlegung hat — Primzahlen sind die irreduziblen Bausteine aller ganzen Zahlen.

Die moderne RSA-Verschlüsselung — die HTTPS-Verkehr und digitale Signaturen absichert — beruht auf Primzahlen. Zwei große Primzahlen zu multiplizieren ist trivial; ihr Produkt in Primzahlen zu zerlegen ist rechnerisch unb- ewältigbar, selbst für moderne Supercomputer. Primzahlen stützen die Sicherheit des Internets.

Weitere Tools in dieser Kategorie