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

... komplette Frage anzeigen

3 Antworten

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 bewerten Vielen Dank für Deine Bewertung

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.

Antwort bewerten Vielen Dank für Deine Bewertung
Kommentar von Epicmetalfan
11.02.2016, 17:26

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

1

Ein schönes video dazu

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

Antwort bewerten Vielen Dank für Deine Bewertung
Kommentar von lisabckr
11.02.2016, 16:49

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

1
Kommentar von googleFTW
11.02.2016, 16:55

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

1

Was möchtest Du wissen?