Probedivision bei Primzahlen nur bis Wurzel?

Question

Um Primzahlen herauszufinden ist eine sehr primitive Methode die Probedivision.

Dabei werden bei einer Zahl n alle Primzahlen bis zu √n durch n geteilt und die Teilbarkeit überprüft. Wenn keine teilbar ist, handelt es sich um eine Primzahl.

Ich hab bereits versucht zu googeln, jedoch bislang keine Erklärung gefunden, wieso nur bis zur Wurzel getestet werden muss. Vermutlich ist die Lösung viel zu einfach, nur bin ich bislang nicht drauf gekommen.

Comments

Kann es keine größeren Teiler als \(\sqrt{n}\) geben?

Answer 1

wenn Du beispielsweise überprüfst, ob 11 eine Primzahl ist, dividierst Du durch

2 | nicht ohne Rest

3 | nicht ohne Rest

Durch 4 brauchst Du nicht zu dividieren, denn 11 ist ja nicht einmal durch 2 ohne Rest zu dividieren. 

Wenn Du jetzt noch die Division durch 5 (>√11) versuchen würdest, müsste, sofern 11 durch 5 teilbar wäre, der andere Faktor aber <√11 sein, was Du aber weiter oben schon abgecheckt hast.

Ist das nachvollziehbar?

Besten Gruß

Comments

Danke erstmal...

Leider nur teilweise - denn könnte es nicht bei anderen Zahlen als 11 anders sein?

---

Gern geschehen :-)

Nein, das ist bei allen Zahlen gleich:

Wenn wir überprüfen wollen, ob eine Zahl n eine Primzahl ist, dann ist maximal ein Faktor > √n;

denn wenn ein Faktor ≥ √n ist und der zweite > √n, haben wir als Produkt schon eine Zahl > n:

√(n+x) * √n > n für x > 0

Zwei andere Beispiele:

9 ist natürlich keine Primzahl; wenn Du bei √9 = 3 angekommen bist und feststellst, dass 3 * 3 = 9 ist, dann brauchst Du den Teiler 4 nicht mehr zu überprüfen; dieser ist > √9, also muss der andere Faktor < √9 sein, und die 2 hast Du ja schon überprüft!

Bei der Primzahl 13 brauchst Du entsprechend nur bis √13 ≈ 3,6 ≈≈ 4 zu überprüfen; wäre z.B. 5 ein Teiler von 13, müsste der andere Teiler zumindest < 4 sein, und die 2 und 3 wurden ja von Dir schon überprüft. 

Etwas klarer?

Besten Gruß

---

Ich verstehe es immer noch nicht

---

Eine Zahl \(n\) hat keine echten Teiler, die größer als \(\sqrt{n}\) sind.