Primzahlen-Rechner

Primzahlen-Rechner - Summe, Anzahl & Primzahlen finden

🔢 Berechnen Sie die Summe von Primzahlen, finden Sie Primzahlen in einem Bereich, prüfen Sie, ob eine Zahl prim ist, und bestimmen Sie die n-te Primzahl. Schnelles Sieb-des-Eratosthenes Verfahren mit Visualisierung.

Was sind Primzahlen?

Eine Primzahl ist eine natürliche Zahl größer als 1, die nicht durch Multiplikation zweier kleinerer natürlicher Zahlen gebildet werden kann. Anders gesagt hat sie genau zwei Teiler: 1 und sich selbst.

Die ersten 25 Primzahlen

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

Wie prüft man, ob eine Zahl prim ist?

Methode 1 - Probeteilung:

• Prüfen Sie, ob n durch eine Zahl von 2 bis √n teilbar ist
• Wenn ja, ist es zusammengesetzt (nicht prim)
• Wenn nein, ist es eine Primzahl

Beispiel: Ist 17 prim?

• √17 ≈ 4,12, also prüfen wir Teilbarkeit durch 2, 3, 4
• 17 ÷ 2 = 8,5 (nicht teilbar)
• 17 ÷ 3 = 5,67 (nicht teilbar)
• 17 ÷ 4 = 4,25 (nicht teilbar)
• Ergebnis: 17 ist eine Primzahl!

Sieb des Eratosthenes

Ein antiker Algorithmus, um alle Primzahlen bis n zu finden:

• Schritt 1: Liste aller Zahlen von 2 bis n
• Schritt 2: Markiere 2 als prim und streiche alle Vielfachen von 2
• Schritt 3: Nächste unmarkierte Zahl (3) finden und als prim markieren
• Schritt 4: Alle Vielfachen dieser Primzahl streichen
• Schritt 5: Wiederholen bis √n
• Ergebnis: Alle ungestrichenen Zahlen sind prim

Summe der Primzahlen

Summe der ersten n Primzahlen:

• Erste 10 Primzahlen: 2+3+5+7+11+13+17+19+23+29 = 129
• Erste 100 Primzahlen: Summe = 24.133
• Erste 1000 Primzahlen: Summe = 3.682.913

Summe der Primzahlen bis n:

• Bis 10: 2+3+5+7 = 17
• Bis 100: Summe = 1.060
• Bis 1000: Summe = 76.127

Primzahlsatz

Die Anzahl der Primzahlen kleiner als n ist ungefähr n/ln(n):

• Bis 100: ~25 Primzahlen (tatsächlich: 25)
• Bis 1.000: ~145 Primzahlen (tatsächlich: 168)
• Bis 10.000: ~1.086 Primzahlen (tatsächlich: 1.229)
• Bis 100.000: ~8.686 Primzahlen (tatsächlich: 9.592)

Arten von Primzahlen

Zwillingsprimzahlen: Primzahlen, die sich um 2 unterscheiden

• (3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43)...

Mersenne-Primzahlen: Form 2ᵖ - 1, wobei p prim ist

• 2² - 1 = 3
• 2³ - 1 = 7
• 2⁵ - 1 = 31
• 2⁷ - 1 = 127
• Die größte bekannte Primzahl ist eine Mersenne-Primzahl (24,8 Millionen Ziffern!)

Sophie-Germain-Primzahlen: Primzahl p, bei der 2p+1 ebenfalls prim ist

• 2 (2×2+1 = 5), 3 (2×3+1 = 7), 5 (2×5+1 = 11), 11, 23, 29...

Fermat-Primzahlen: Form 2^(2ⁿ) + 1

• F₀ = 3, F₁ = 5, F₂ = 17, F₃ = 257, F₄ = 65.537
• Es sind nur 5 Fermat-Primzahlen bekannt

Anwendungen von Primzahlen

Kryptografie (RSA):

• Basiert auf der Schwierigkeit, große Zahlen zu faktorisieren
• Verwendet zwei große Primzahlen (Hunderte von Ziffern)
• Sichert Online-Banking, E-Mails und Websites

Hash-Tabellen:

• Hash-Tabellen mit primzahliger Größe reduzieren Kollisionen
• Werden in Datenbanken und Caches eingesetzt

Zufallszahlengenerierung:

• Primzahlen erzeugen bessere pseudorandomisierte Sequenzen
• Verwendet in Simulationen und Spielen

Interessante Fakten über Primzahlen

• Unendlichkeit: Von Euklid ~300 v. Chr. bewiesen – Primzahlen enden nie
• Lücken: Können beliebig groß sein (keine Primzahlen über Millionen aufeinanderfolgender Zahlen)
• Goldbachsche Vermutung: Jede gerade Zahl > 2 ist Summe zweier Primzahlen (unbewiesen!)
• Riemannsche Vermutung: Million-Dollar-Preis für einen Beweis zur Primzahlverteilung
• Primzahllücken: Abstände zwischen aufeinanderfolgenden Primzahlen werden größer
• Wahrscheinlichkeit: Eine Zufallszahl n hat ungefähr 1/ln(n) Chance, prim zu sein

Primzahl-Rekorde

• Größte bekannte Primzahl: 2^82,589,933 - 1 (entdeckt 2018, 24.862.048 Ziffern)
• Größte Zwillingsprimzahlen: 2.996.863.034.895 × 2^1.290.000 ± 1
• Berechnung: GIMPS (Great Internet Mersenne Prime Search) – verteiltes Projekt

Häufige Irrtümer

• 1 ist KEINE Primzahl: Nach moderner Definition (genau 2 Teiler)
• Nicht alle ungeraden Zahlen sind prim: 9, 15, 21, 25... sind zusammengesetzt
• Formel für alle Primzahlen: Es gibt keine einfache Formel, die alle Primzahlen erzeugt
• Muster in Primzahlen: Kein vorhersehbares Muster (wirken zufällig)

💡 Profi-Tipp: Um zu prüfen, ob eine große Zahl prim ist, reicht es, Teiler nur bis zur Quadratwurzel zu testen! Zum Beispiel braucht man für 997 nur bis √997 ≈ 31,6 zu prüfen, also 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31. Wenn keiner davon 997 ohne Rest teilt, ist sie prim! Diese Optimierung macht die Primzahlprüfung deutlich schneller. Außerdem sind (außer 2 und 3) alle Primzahlen von der Form 6k±1, was die Suche zusätzlich beschleunigen kann!