Frage von Jonaschecker123, 168

Gibt es keinen Algorithmus mit den man Primzahlen berechnen kann?

Antwort
von Roderic, 158

Du redest sicherlich nicht von kleinen Primzahlen sondern von großen - richtig großen.

Ja - natürlich gibt es da Algorithmen.

Die eigentliche Frage ist jedoch, gibt es auch welche, die beliebig große Primzahlen mit einem vertretbaren Aufwand an Zeit berechnen können?

Da lautet die Antwort: Bisher noch nicht.

Antwort
von BrilleHN, 168

Warum sollte es keinen Algorithmus dafür geben.

Die Regel ist eifach: Eine Primzahl darf nur durch 1 oder sich selbst teilbar sein.

Du brauchst eine Endlosschleife in der die zu prüfende Zahl hoch gezählt wird

Dann fügst Du eine zweite Schleife in die Endlosschleife ein und in dieser teilst Du eine Zahl durch einen zweiten Counter. Der Rest darf maximal 2 mal Null sein, ansonsten brichst du die zweite Schleife ab sobald der Counter gleich groß wie die Zahl ist und schreibst die Zahl in ein variables Array.

Antwort
von phigeek, 133

Ein sehr einfacher Algorithmus ist das Sieb des Eratosthenes. Dabei wird in einer lückenloser (endlicher) Liste ab der Zahl 2 sukzessive nach folgendem Vorgehen gestrichen. Zurück bleiben die Primzahlen.

Das geht wie folgt (Beispiel alle Primzahlen bis bis 20). Beginne mit der lückenlosen Liste:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

  1. Streiche alle Vielfachen von 2 (lasse die 2 als Primzahl stehen). Es bleibt:

2 3 5 7 9 11 13 15 17 19

  1. Streiche alle Vielfchen von 3 (lasse die 3 als Primzahl stehen). Es bleibt:

2 3 5 7 11 13 17 19

Die nächste Primzahl ist 5. Da diese jedoch bereits größer ist, als die Wurzel von 20, sind wir fertig: Wir mit einer vollständigen Liste aller Primzahlen bis 20 beglückt worden.

Antwort
von eulemitderbeule, 135

leider noch nicht. Annäherungsfunktionen gibt es, mit Logarithmus z.B.

bin auch schon seit langem dabei einen zu finden,

dann würde ich die Fields-Medaille bekommen.

Kommentar von Jonaschecker123 ,

hab ich auch mal probiert und mir die Zähne ausgebissen! Hätte fast geklappt! :(

Keine passende Antwort gefunden?

Fragen Sie die Community