0 Daumen
1k Aufrufe

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.

Avatar von 14 k

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.

1 Antwort

+2 Daumen

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}\).

Avatar von

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.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community