Frage von lisabckr, 129

Herausfinden, ob es sich um eine Primzahl handelt (große Zahlen)?

Wie kann man bei großen Zahlen (beispielsweise 4.000 stellig) herausfinden, ob es sich um eine Primzahl handelt?

Antwort
von Schachpapa, 94

Da gibt es spezielle Verfahren https://de.wikipedia.org/wiki/Primzahltest

Der Nachweis, dass eine Zahl prim ist, ist bedeutend einfacher als die Zerlegung einer nicht primen Zahl in ihre Faktoren. Letzteres ist bei einer beliebigen 4000 stelligen Zahl mit heutigen Methoden nicht möglich (prinzipiell schon dauert aber "ewig").

Antwort
von daCypher, 91

Ich glaub, da werden einfach alle Zahlen von einem Computer durchgerechnet. Wenn es dann bis zur Wurzel aus der Zahl keine Zahl gab, durch die sie ganzzahlig teilbar ist, ist es eine Primzahl. Bei den meisten Zahlen kann man ganz schnell berechnen, dass es keine Primzahl ist und beim durchrechnen der Zahlen reicht es auch, wenn man nur prüft, ob die Zahl durch eine andere Primzahl teilbar ist. Wenn eine Zahl z.B. nicht durch eine 2 teilbar ist, ist sie auch nicht durch eine 4, 6, 8 etc. teilbar.

Kommentar von Epicmetalfan ,

naja die wurzel einer 4000stelligen zahl ist immernoch 2000 stellig. selbst wenn du davon ausgehst, dass ein computer pro sekunde 10^9 zahlen prüfen kann, bräuchte er demnach 10^1991 sekunden um alle zahlen zu testen. zum vergleich, unser universum ist ca 4*10^17 sekunden alt

der computer bräuchte also buchstäblich ewig.

klar musst du an sich nur die primzahlen testen, wie du schon sagtest, aber selbst damit würde er noch ewig brauchen.

diese methode funktioniert einfach nur bei kleinen zahlen

Antwort
von googleFTW, 82

Ein schönes video dazu

Der kanal ist nur zu empfehlen :d ist allerdings auf englisch.

Kommentar von lisabckr ,

Vielen Dank! Englisch ist für mich gar kein Problem

Kommentar von googleFTW ,

dann wird dir der kanal gefallen :D falls du die videos durchsuchtest und nachschub brauchst: die besten videos macht james grime. der hat einen eigenen kanal namens singingbanana

Keine passende Antwort gefunden?

Fragen Sie die Community

Weitere Fragen mit Antworten