Frage zur Berechnung von Primzahlen (Math. Beweis)?
Hey Leute,
ich habe gerade etwas mit Primzahlen und deren Berechnung herumgespielt und bin dabei auf was interessantes gestoßen, wofür ich leider keine Erklärung finde.
Ich habe ein kleines Programm in Java geschrieben, welches mir Primzahlen berechnen soll.
Mein 1. Ansatz war, zu überprüfen, ob alle Zahlen bis n durch n teilbar sind. Also bspw. bei 37 habe ich geschaut, ob die Zahlen von 2 - 36 Teiler von 37 sind.
Mein 2. Ansatz war dann, nur noch bis zur Hälfte der Zahl zu überprüfen, da es ab der Hälfte ja definitiv nicht mehr teilbar ist. Also bspw. bei 37 habe ich geschaut, ob die zahlen von 2 - (37/2) also 2 - 18 Teiler von 37 sind.
Mein 3. Ansatz war jetzt, nur noch bis zur Quadratwurzel+1 der Zahl zu überprüfen und scheinbar funktioniert das auch. Also bspw. bei 37 habe ich geschaut, ob die Zahlen von 2 - WURZEL(37)+1 also 2 - 7 Teiler von 37 sind.
Mich würde jetzt nur interessieren, wieso das funktioniert.
Hier mein Code, falls relevant: https://paste.helpch.at/debacameco.java
Mfg Jannick (L1nd)
Meintest du n durch 37? Oder 37 durch n?
natürlich 37 durch n. Anfrage auf Änderung der Frage ist schon raus
5 Antworten
Du meinst es hoffentlich umgekehrt:
Du hast geschaut, ob 37 durch eine Zahl 2-36 teilbar ist. Ob 2-36 durch 37 teilbar sind (so hast duces geschrieben) brauchst du nicht prüfen, das ist ausgeschlossen.
Zu den Grenzen: die Quadratwurzel ist das Optimum.
WENN eine Zahl keine Quadratzahl ist, so gibt es immer paarweise Teiler, von denen einer kleiner, der andere größer sein muss als die Wurzel. Und den kleineren findest du mit deinen Tests, mehr brauchst du nicht.
Super, vielen Dank. Ich glaube jetzt hab ich das verstanden und es ist ja tatsächlich gar nicht so schwer :D
Die Frage hab ich bereits geändert, sie macht jetzt hoffentlich mehr Sinn
Du hast geschaut ob 2-18 durch 37 teilbare sind, meinst du nicht andersrum? Das 37 dadurch teilbar ist
Hoppla, ja natürlich meinte ich das so rum, ändere das fix
Das hatte wohl Eratosthenes schon erkannt:
"Da mindestens ein Primfaktor einer zusammengesetzten Zahl immer kleiner gleich der Wurzel der Zahl sein muss"
und in seinem Sieb des Eratosthenes berücksichtigt.
Das mit der Qudratwurzel ist der richtige (weil optimale) Ansatz.
Wenn n einen Teiler hat, der größer als die Wurzel ist, dann muss es auch einen Teiler geben, der kleiner oder gleich der Wurzel ist.
Andersrum gesagt: Wenn man bis zur Wurzel keinen Teiler gefunden hat, dann gibt es auch keinen darüber. (außer n selbst)
leider finde ich das gerade nicht , aber das "sieb des ...." zeigt diese schlüssigkeit das es auch mit der Wurzel geht . bzw man wirklich wenige zahlen brauch , da die unteren teiler dann eh alle weg sind und die vielfachen ja im oberen bereich eh deutlich zunhemen
wenn was durch 18 teilbar ist ist es auch durch 9 teilbar oder auch durch 3 , da brauch ich 18 gar nicht mehr testen .
p.s. da gibts gute videos zu die dir zeigen, wie weit man überhaupt testen muss .
Sieb des Eratosthenes
Achsoo, ich glaube ich weiss was du meinst. Nehmen wir mal 36 als Beispiel. Dann reicht es bis zur Quadratwurzel von 6 zu testen, da wenn ich auf 7 testen würde, die andere Seite kleiner werden müsste (da sonst größer 36) und die kleineren Teiler habe ich ja schon überprüft. Hoffe man versteht was ich meine
Ein bisschen unglücklich formuliert
bis zur Quadratwurzel von 6
Gemeint ist hier 6 als Quadratwurzel von 36.
Ich verstehe, was Du meinst und es ist richtig so.
Hoppla, heute ist nicht mein Tag, Frage falsch formuliert, den Kommentar falsch formuliert. Trotzdem Danke :)
Als zusätzliche Optimierung habe ich auch noch eingefügt, dass die zu testenden Teiler nicht alle Zahlen von 2 - WURZEL(n)+1 sind, sondern nur die ungeraden Zahlen von 3 - WURZEL(n)+1. Das ist doch immer noch richtig, da jede gerade Zahl ja auch durch 2 teilbar wäre und somit direkt rausfällt, oder?