Primzahltest nur bis Wurzel aus n? Primzahltest nur bis [√n]

Question

Es geht um eine natürliche Zahl n, die auf die Primzahleigenschaft geprüft wird. Wie kommt man aufeinmal darauf, dass es sogar genügt sich nur Zahlen $$ i< \lfloor{\sqrt{n}}\rfloor $$ als potenzielle Teiler anzuschauen?

Trotz durchgerechneter Beispiele wird das einfach nicht klar.

Comments

EDIT: Warum wurde meine Frage hier her verschoben? Es ging mir bei der Frage primär darum, warum man den Primzahltest als Algorithmus auch so gestalten kann, Zahlen bis höchstens ⌊√(.)⌋ zu betrachten.

---

Eigentlich brauchst du ≤ . D.h.

$$ i≤ \lfloor{\sqrt{n}}\rfloor $$

Aber, wenn du die Wurzel ausrechnest, und merkst, dass diese eine natürliche Zahl ist, kannst du dir den Test sparen. n ist dann ja keine Primzahl.

---

Du musst ja √(n) gar nicht unbedingt ausrechnen.

Lasse die a von 2 bis beliebig laufen und rechne:

n / a = b

falls b ein Integer -> keine Primzahl -> fertig

falls b > a , erhöhe a um 1, und gehe nochmals in die Schleife mit der Division

sonst, ==> n ist Primzahl.

Answer 1

Teiler kommen immer zu zweit. Wenn \(n=ab\), koennen nicht beide Teiler \(a\) und \(b\) groesser oder beide kleiner als \(\sqrt{n}\) sein, denn sonst ist das Produkt \(ab\) zu gross oder zu klein. Es ist also immer einer \(\le\sqrt{n}\) und einer \(\ge\sqrt{n}\).

Comments

Ginge auch folgende Überlegung/Behauptung?

$$ \text{Seien }a,b,n\in\mathbb{N}_{\geq 1}\text{ mit }n=a\cdot b\\\text{gegeben, wobei n keine Quadratzahl ist. Dann gilt für beide Faktoren}\\a\leq\sqrt{n}\leq b\text{ oder }a\geq\sqrt{n}\geq b.\\[20pt]\text{Beweis. Da n keine Quadratzahl ist, folgt auch }a\neq b.\\\text{Angenommen es gelte für beide Faktoren }a,b\\a<\sqrt{n}<b\text{ und }a>\sqrt{n}>b. \text{ Dann muss auch }a<\sqrt{n}<\sqrt{n}<a\\\text{gelten, was aber offensichtlich ein Widerspruch zur Annahme ist.}\\\text{Damit folgt die Beahuptung.}  $$

---

Deine Behauptung gilt immer. Auch wenn n ein Quadrat ist.

---

Das ist mir klar, dass das dann erst recht gilt. Deshalb habe ich diesen Fall ausgeschlossen.