Primfaktorzerlegung Rechner und Primzahltest

Primfaktorzerlegung und Primzahltest in einem Rechner

Dieser Primfaktorzerlegung Rechner beantwortet zwei Fragen aus dem Matheunterricht: Ist die Zahl eine Primzahl, und wie lautet ihre Zerlegung in Primfaktoren? Geben Sie eine ganze Zahl mit bis zu 40 Stellen ein. Sie erhalten das Ergebnis, das verwendete Verfahren, die Zerlegung in Potenzschreibweise (etwa 2³ × 3² × 5), die Anzahl der Teiler, alle Teiler sowie die vorherige und die nächste Primzahl. Ein zweiter Modus listet alle Primzahlen bis 10 Millionen auf.

So funktioniert es

1. Wählen Sie „Zahl prüfen und zerlegen“, tragen Sie die Zahl unter „Ganze Zahl“ ein und klicken Sie auf „Prüfen“ oder drücken Sie die Eingabetaste. Auch Potenzen gehen: 2^61 − 1.
2. Sie sehen die „Primfaktorzerlegung“, die „Anzahl der Teiler“, die „Vorherige Primzahl“ und die „Nächste Primzahl“. Unter „Fortgesetzte Division“ steht der Rechenweg.
3. Mit „Faktorbaum anzeigen“ erscheint der Faktorbaum, mit „Alle Teiler anzeigen“ die Teilermenge samt Summe.
4. Für eine Liste wählen Sie „Liste der Primzahlen“, geben N unter „Primzahlen bis N“ ein und klicken auf „Liste anzeigen“. „Liste herunterladen (.txt)“ speichert die vollständige Liste.

Was man über Primzahlen wissen sollte

Eine Primzahl ist eine natürliche Zahl mit genau zwei Teilern: 1 und sich selbst. 2, 3, 5, 7, 11 und 13 sind Primzahlen, 2 ist die einzige gerade. 1 ist keine Primzahl, denn sie hat nur einen Teiler; auch 0 ist keine. Zahlen größer als 1, die keine Primzahlen sind, heißen zusammengesetzt.

Um eine Primzahl zu prüfen, teilt man probeweise durch alle Zahlen von 2 bis zur Wurzel der Zahl. Bei 97 ist √97 ≈ 9,8, und weder 2 noch 3, 5 oder 7 teilen 97: Sie ist eine Primzahl. Vorsicht bei 57: Sie sieht prim aus, doch 57 = 3 × 19. Bei sehr großen Zahlen nutzt der Rechner den Miller-Rabin-Test, der für alle Zahlen bis 2⁶⁴ und weit darüber hinaus ein bewiesenes Ergebnis liefert.

So zerlegt man eine Zahl in Primfaktoren

Man teilt durch die kleinste Primzahl, solange die Division aufgeht, und nimmt dann die nächste. Bei 2016: 2016 ÷ 2 = 1008, ÷ 2 = 504, ÷ 2 = 252, ÷ 2 = 126, ÷ 2 = 63, 63 ÷ 3 = 21, 21 ÷ 3 = 7, 7 ÷ 7 = 1. Also ist 2016 = 2⁵ × 3² × 7. Diese Zerlegung ist bis auf die Reihenfolge eindeutig. Sie liefert auch die Anzahl der Teiler: Jeden Exponenten um 1 erhöhen und multiplizieren, 6 × 3 × 2 = 36 Teiler. Die benachbarten Primzahlen sind 2011 und 2017.

Gebraucht wird die Zerlegung zum Kürzen von Brüchen sowie für ggT und kgV.

Das Sieb des Eratosthenes

Für alle Primzahlen bis N schreibt man die Zahlen von 2 bis N auf, behält die 2 und streicht ihre Vielfachen, behält die nächste nicht gestrichene Zahl, 3, und streicht deren Vielfache, und so weiter. Bis 100 genügt es, die Vielfachen von 2, 3, 5 und 7 zu streichen: Es bleiben 25 Primzahlen. Bis 10 Millionen sind es 664.579; der Rechner findet sie in deutlich unter einer Sekunde.

Es gibt unendlich viele Primzahlen, wie Euklid schon vor über 2000 Jahren bewiesen hat. Manche Verschlüsselungsverfahren beruhen darauf, dass es mit den bekannten Methoden enorm aufwendig ist, zwei große Primzahlen mit Hunderten von Stellen aus ihrem Produkt zurückzugewinnen.

Häufige Fragen

Warum ist 1 keine Primzahl?

Eine Primzahl braucht genau zwei verschiedene Teiler, die 1 hat nur einen. Außerdem bleibt die Primfaktorzerlegung so eindeutig: Sonst könnte man 6 als 2 × 3, 1 × 2 × 3, 1 × 1 × 2 × 3 usw. schreiben.

Wie groß darf die Zahl sein?

Bis zu 40 Stellen. Der Primzahltest ist fast sofort fertig. Ist die Zahl das Produkt zweier großer Primzahlen, kann die Zerlegung dauern: Nach 10 Sekunden bricht der Rechner ab und nennt den Faktor, der nicht zerlegt werden konnte.

Ist 2⁶¹ − 1 eine Primzahl?

Ja: 2⁶¹ − 1 = 2.305.843.009.213.693.951 ist eine Mersenne-Primzahl. Geben Sie 2^61 − 1 ein, um es zu prüfen. Die größte Primzahl unter 2⁶⁴ ist 18.446.744.073.709.551.557.