Primfaktorzerlegung obere Grenze

12.05.2020, 20:21	wuschelhaeschen97	Auf diesen Beitrag antworten »
Primfaktorzerlegung obere Grenze Meine Frage: Die Frage bezieht sich auf die Primfaktorzerlegung und es wird eine obere Grenze für die Primfaktorzerlegung gesucht. Also eine Zahl n, ab der kein Primfaktor für eine weitere Zerlegung mehr gefunden werden kann. Das so genannte (Abbruchkriterium)2 Meine Ideen: Die PFZ zerlegt ja immer in Primzahlen und dabei die größtmöglichen. Dann müsste n ja eigentlich die größte Primzahl gegen unendlich sein. Aber wie gibt man die an?
12.05.2020, 20:28	HAL 9000	Auf diesen Beitrag antworten »
Ich würde die Frage eher so verstehen, dass man für eine vorgegebene Zahl $\begin{eqnarray} m \end{eqnarray}$ eine obere Grenze $\begin{eqnarray} n \end{eqnarray}$ für die zu untersuchenden möglichen Primteiler $\begin{eqnarray} p \end{eqnarray}$ von $\begin{eqnarray} m \end{eqnarray}$ angeben soll: D.h. mit der Eigenschaft, wenn man keine solchen Primteiler $\begin{eqnarray} p\leq n \end{eqnarray}$ gefunden hat, dann soll $\begin{eqnarray} m \end{eqnarray}$ sicher selbst eine Primzahl sein. Diese Zahl ist $\begin{eqnarray} n = \left\lfloor \sqrt{m}\right\rfloor \end{eqnarray}$ , warum?
12.05.2020, 21:00	wuschelhaschen97	Auf diesen Beitrag antworten »
Prinzipiell heißt das, dass wenn die PFZ von m gefragt ist und m eine Primzahl ist, dann müsste m doch gleich n sein
13.05.2020, 07:09	HAL 9000	Auf diesen Beitrag antworten »
Nein: Es geht ja nicht darum, dass $\begin{eqnarray} n \end{eqnarray}$ ein Teiler von $\begin{eqnarray} m \end{eqnarray}$ ist, sondern nur, dass man für alle Primzahlen $\begin{eqnarray} p\leq n \end{eqnarray}$ prüft, ob sie $\begin{eqnarray} m \end{eqnarray}$ teilen!!! Beispiel: $\begin{eqnarray} m=53 \end{eqnarray}$ , da ist $\begin{eqnarray} n=\left\lfloor \sqrt{53}\right\rfloor = \left\lfloor 7.28\right\rfloor = 7 \end{eqnarray}$ Man prüft daher die Teilbarkeit von 53 durch 2, 3, 5, 7, das sind alles Fehlschläge, woraufhin man weiß, dass 53 eine Primzahl ist. Warum kann man das machen? Wenn es einen Primteiler $\begin{eqnarray} \sqrt{m}< p < m \end{eqnarray}$ gibt, dann ist $\begin{eqnarray} m \end{eqnarray}$ auch durch dessen Komplementärteiler $\begin{eqnarray} q:=\frac{m}{p} \end{eqnarray}$ teilbar. Für den gilt aber $\begin{eqnarray} 1 < q < \sqrt{m} \end{eqnarray}$ und damit $\begin{eqnarray} 1 < q \leq n \end{eqnarray}$ , man findet also bereits $\begin{eqnarray} q \end{eqnarray}$ bzw. besser gesagt dessen kleinsten Primteiler in der obigen Untersuchung. Wenn also kein solch "kleiner" Teiler gefunden wurde, dann gibt es auch diese großen Teiler $\begin{eqnarray} \sqrt{m}< p < m \end{eqnarray}$ nicht.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »