Primzahlrechner

21.11.2022, 13:54

Prim3241

Primzahlrechner

Es geht um Primzahlen. Wir haben in der Schule ein Programm geschrieben, über Primzahlen.

Es geht mir nur um die mathematische Logik. Und zwar war es so, dass es eine zu überprüfende Zahl gab, nehmen wir mal als Beispiel die 20.

Jetzt müsste man ja überprüfen, ob die Zahl Teiler hat und zwar von 2 bis 19, ob eine dieser Zahlen durch 20 teilbar ist.

In der Schule haben wir aber jetzt nicht die Zahlen von 2 bis 19 überprüft, sondern von 2 bis Wurzel(20).

Kann mir jemand vielleicht sagen, warum das so geht?

Equester: MultiBeiträge zusammengefügt.

21.11.2022, 14:17

HAL 9000

Auf diesen Beitrag antworten »

Man betrachte den kleinsten Teiler $\begin{eqnarray*} t>1 \end{eqnarray*}$ der Zahl $\begin{eqnarray*} n \end{eqnarray*}$ (das ist logischerweise auch eine Primzahl, was aber im folgenden nicht wichtig ist):

1. Ist $\begin{eqnarray*} n \end{eqnarray*}$ Primzahl, so ist $\begin{eqnarray*} t=n \end{eqnarray*}$ .

2. Ist $\begin{eqnarray*} n \end{eqnarray*}$ keine Primzahl, so ist $\begin{eqnarray*} 1<t<n \end{eqnarray*}$ . Mit $\begin{eqnarray*} t \end{eqnarray*}$ ist nun aber auch die Zahl $\begin{eqnarray*} \frac{n}{t} \end{eqnarray*}$ ein Teiler von $\begin{eqnarray*} n \end{eqnarray*}$ , es gilt dann ebenso $\begin{eqnarray*} 1<\frac{n}{t}<n \end{eqnarray*}$ , und da $\begin{eqnarray*} t \end{eqnarray*}$ voraussetzungsgemäß der kleinste Teiler >1 von $\begin{eqnarray*} n \end{eqnarray*}$ ist, muss auch $\begin{eqnarray*} t\leq \frac{n}{t} \end{eqnarray*}$ gelten.

Umgestellt heißt das $\begin{eqnarray*} t^2\leq n \end{eqnarray*}$ und folglich $\begin{eqnarray*} t\leq \sqrt{n} \end{eqnarray*}$ , was nichts anderes bedeutet, dass man solche Teiler $\begin{eqnarray*} t \end{eqnarray*}$ nur bis $\begin{eqnarray*} \sqrt{n} \end{eqnarray*}$ suchen muss. Gibt es keinen solchen, wissen wir sofort, dass Fall 1., also $\begin{eqnarray*} n \end{eqnarray*}$ Primzahl vorliegt.

21.11.2022, 14:19

Elvis

Auf diesen Beitrag antworten »

Es genügt, zu prüfen, ob 20 durch Primzahlen kleiner Wurzel aus 20 teilbar ist. Wenn es nicht so wäre, und es einen Teiler größer als Wurzel 20 gäbe, müsste ein anderer Teiler kleiner gleich Wurzel 20 sein.

Beispiel: 20=2*10, 10=2*5 fertig.

21.11.2022, 15:16

mYthos

Auf diesen Beitrag antworten »

Man spricht von Komplementärteilern

Zu dem Teiler 2 von 100 existiert der Komplemtärteiler 50.
Zu dem Teiler 4 von 100 existiert der Komplemtärteiler 25.
Zu dem Teiler 5 von 100 existiert der Komplemtärteiler 20.
Zu dem Teiler 10 von 100 gibt es den Komplentärteiler (ebenfalls) 10

Sind alle Teiler bis 10 geprüft, kann man also das Verfahren beenden.

mY+

21.11.2022, 15:25

HAL 9000

Auf diesen Beitrag antworten »

Danke für die Ergänzung dieser Bezeichnung. Hatte ich oben in meinem Text bei diesem $\begin{eqnarray*} \frac{n}{t} \end{eqnarray*}$ noch anmerken wollen, es dann aber vergessen.

21.11.2022, 21:53

Prim3241

Auf diesen Beitrag antworten »

Zitat:

Man spricht von Komplementärteilern

Zu dem Teiler 2 von 100 existiert der Komplemtärteiler 50.
Zu dem Teiler 4 von 100 existiert der Komplemtärteiler 25.
Zu dem Teiler 5 von 100 existiert der Komplemtärteiler 20.
Zu dem Teiler 10 von 100 gibt es den Komplentärteiler (ebenfalls) 10

Sind alle Teiler bis 10 geprüft, kann man also das Verfahren beenden.

mY+

Wurden die Teiler 3,6,7,8 mit Absicht ausgelassen? Wenn ja, wieso wenn ich fragen darf?

21.11.2022, 21:54

Prim3241

Auf diesen Beitrag antworten »

Ah, weil sie keine Teile von 100 sein können.

21.11.2022, 21:56

Prim3241

Auf diesen Beitrag antworten »

Kann man den Algorithmus dann nicht noch effizienter machen? Indem man von vornerein die Zahlen, die keine Teiler sein können, weglässt. verwirrt

21.11.2022, 22:01

Prim3241

Auf diesen Beitrag antworten »

Vergiss was ich gefragt habe, ich glaub, das geht nicht. Angenommen ich nehme 100, müsste ich trotzdem überprüfen, ob zum Beispiel 3 durch 100 teilbar ist oder ich müsste mehr über die Zahl 100 wissen.

Danke euch allen.

21.11.2022, 22:34

mYthos

Auf diesen Beitrag antworten »

Zitat:

Original von Prim3241
...
Angenommen ich nehme 100, müsste ich trotzdem überprüfen, ob zum Beispiel 3 durch 100 teilbar ist ..
....

Du meinst wohl, ob 100 durch 3 teilbar ist.

Es geht einfacher, wenn du eine Zerlegung in Primfaktoren (ohne 1) durchführst.

100 = 2*2*5*5

Nun sind alle Teiler von 100 alle möglichen Produkte dieser Linearfaktoren 2,2,5,5:
2, 4, 5, 10, 20, 25, 50
Und, wie gesagt, man braucht nur bis 10 zu gehen, danach kommen die Komplementärteiler ...

mY+

22.11.2022, 14:19

Prim3241

Auf diesen Beitrag antworten »

Ohh smart! Danke sehr.

22.11.2022, 14:24

Elvis

Auf diesen Beitrag antworten »

Na klar ist das smart. Das ist ja auch genau das, was ich am 21.11.2022 um 14:19 gemacht habe. Die Zahl, die man zerlegen will teilt man durch den kleinsten Primteiler, dann geht's mit dem Komplementärteiler genau so weiter. Rekursion ist das, was Algorithmen am besten können.

Neue Frage »

Antworten »

Primzahlrechner

Verwandte Themen