Primzahlen

Manche Zahlen lassen sich einfach nicht ordentlich aufteilen. 12 Kekse kannst du in Zweier-, Dreier-, Vierer- oder Sechserreihen legen. Bei 13 Keksen? Keine Chance, außer alle in eine Reihe. Solche sturen Zahlen heißen Primzahlen, und sie sind viel mehr als eine Kuriosität: Ohne sie würde kein Online-Banking funktionieren.

Genau zwei Teiler

Eine Primzahl ist eine Zahl, die genau zwei Teiler hat: die 1 und sich selbst. 7 ist prim, denn nur 1 und 7 teilen sie ohne Rest. 6 ist nicht prim, denn 1, 2, 3 und 6 sind Teiler. Die 1 zählt übrigens nicht als Primzahl, sie hat ja nur einen einzigen Teiler. Die kleinsten Primzahlen sind 2, 3, 5, 7, 11, 13, und die 2 ist die einzige gerade Primzahl überhaupt: Jede andere gerade Zahl hat ja die 2 als zusätzlichen Teiler. Im Punktefeld siehst du das sofort: 12 Punkte lassen sich als mehrere verschiedene Rechtecke legen, 13 Punkte nur als eine einzige Reihe.

Das Sieb des Eratosthenes

Wie findet man alle Primzahlen bis 100? Schon vor über 2000 Jahren hatte der Grieche Eratosthenes eine schlaue Idee: Schreibe alle Zahlen von 2 bis 100 auf und streiche der Reihe nach die Vielfachen. Erst alle Vielfachen von 2, dann von 3, dann von 5, und so weiter, wobei die Zahl selbst jeweils stehen bleibt. Du nimmst dir dabei immer die kleinste Zahl vor, die noch nicht gestrichen ist, deshalb folgt auf die 3 nicht die 4, sondern die 5. Was am Ende nicht gestrichen ist, muss eine Primzahl sein: ein Sieb, das alle zerlegbaren Zahlen durchfallen lässt.

Zahlen in Bausteine zerlegen

Jede Zahl größer als 1 lässt sich als Produkt von Primzahlen schreiben, und zwar bis auf die Reihenfolge der Faktoren auf genau eine Weise. Das nennt man Primfaktorzerlegung. Beispiel: 12 = 2 · 2 · 3 oder 30 = 2 · 3 · 5. Du findest sie, indem du immer wieder durch die kleinste passende Primzahl teilst. Primzahlen sind also die Bausteine, aus denen alle anderen Zahlen zusammengesetzt sind. Und genau das macht sie so wertvoll: Bei riesigen Zahlen ist diese Zerlegung selbst für Computer extrem schwer, und darauf beruht die Verschlüsselung, die deine Passwörter und Nachrichten schützt.