Warum prüft man bis zur Quadratwurzel einer Zahl, ob die Zahl eine Primzahl ist?

Question

Warum muss man, um zu prüfen, ob eine Zahl eine Primzahl ist oder nicht, prüfen, ob sie nur bis zur Quadratwurzel dieser Zahl teilbar ist?

Answer 1

Nehmen wir an, dass die gegebene ganze Zahl N nicht primär ist,

Dann kann N in zwei Faktoren faktorisiert werden a y b , 2 <= a, b < N tal que N = a*b . Beide können natürlich nicht größer sein als sqrt(N) gleichzeitig.

Nehmen wir ohne Verlust der Allgemeinheit an, dass a kleiner ist.

Wenn Sie nun keinen Teiler von N die in den Bereich [2, sqrt(N)] Was soll das bedeuten?

Dies bedeutet, dass N hat keinen Teiler in [2, a] als a <= sqrt(N) .

Deshalb, a = 1 y b = n und daher Per Definition, N ist primär .

...

Lesen Sie weiter, wenn Sie nicht zufrieden sind:

Viele verschiedene Kombinationen von (a, b) möglich sein. Nehmen wir an, sie sind es:

(a ₁ , b ₁ ), (a ₂ , b ₂ ), (a ₃ , b ₃ ), ..... , (a _k , b _k ). Ohne Verlust der Allgemeingültigkeit wird angenommen, dass a _i < b _i , 1<= i <=k .

Um nun zeigen zu können, dass N nicht prim ist, genügt es zu zeigen, dass keine der a _i kann weiter faktorisiert werden. Und wir wissen auch, dass a _i <= sqrt(N) und daher müssen Sie prüfen, bis sqrt(N) die sich auf alle A _i . So können Sie feststellen, ob N ist primär.

...

Answer 2

Um also zu prüfen, ob eine Zahl N Primzahl ist oder nicht. Wir brauchen nur zu prüfen, ob N durch Zahlen<=SQROOT(N) teilbar ist. Das liegt daran, dass, wenn wir N in 2 beliebige Faktoren, sagen wir X und Y, zerlegen, d.h. N=X Y. Sowohl X als auch Y können nicht kleiner als SQROOT(N) sein, denn dann würde X Y < N X und Y können nicht größer sein als SQROOT(N), denn dann ist X*Y > N

Daher muss ein Faktor kleiner oder gleich SQROOT(N) sein (während der andere Faktor größer oder gleich SQROOT(N) ist). Um zu prüfen, ob N Primzahl ist, müssen wir also nur die Zahlen <= SQROOT(N) prüfen.

Answer 3

Nehmen wir an, wir haben eine Zahl "a", die nicht prim ist [nicht prim/zusammengesetzte Zahl bedeutet - eine Zahl, die gleichmäßig durch andere Zahlen als 1 oder sich selbst geteilt werden kann. Zum Beispiel kann 6 gleichmäßig durch 2 oder durch 3 sowie durch 1 oder 6 geteilt werden].

6 = 1 × 6 oder 6 = 2 × 3

Wenn also "a" keine Primzahl ist, dann kann es durch zwei andere Zahlen geteilt werden, und sagen wir, diese Zahlen sind "b" und "c". Das bedeutet

a=b*c.

Wenn nun "b" oder "c" größer ist als die Quadratwurzel von "a", dann ist die Multiplikation von "b" und "c" größer als "a".

Also ist "b" oder "c" immer <= Quadratwurzel von "a", um die Gleichung "a=b*c" zu beweisen.

Aus diesem Grund wird bei der Prüfung, ob eine Zahl eine Primzahl ist oder nicht, nur bis zur Quadratwurzel dieser Zahl geprüft.

Answer 4

Bei einer beliebigen Zahl n ist eine Möglichkeit, seine Faktoren zu ermitteln, indem man seine Quadratwurzel bildet p :

sqrt(n) = p

Natürlich, wenn wir multiplizieren p von selbst, dann erhalten wir zurück n :

p*p = n

Sie kann umgeschrieben werden als:

a*b = n

Wo p = a = b . Si a steigt, dann b sinkt zur Aufrechterhaltung a*b = n . Deshalb, p ist die Obergrenze.

Aktualisierung: Ich habe diese Antwort heute noch einmal gelesen, und sie ist mir noch klarer geworden. Der Wert p bedeutet nicht notwendigerweise eine ganze Zahl, denn wenn sie es ist, dann n wäre keine Primzahl. Also, p könnte eine reelle Zahl sein (d.h. mit Brüchen). Und anstatt den gesamten Bereich der n müssen wir jetzt nur noch den gesamten Bereich der p . Die andere p ist eine gespiegelte Kopie, so dass sich der Bereich in Wirklichkeit halbiert. Und dann, jetzt sehe ich, dass wir tatsächlich die Wiederholung der square root und es zu tun p zur weiteren Halbierung der Reichweite.

Answer 5

N sei eine Nicht-Primzahl. Es hat also mindestens zwei ganzzahlige Faktoren, die größer als 1 sind. f sei der kleinste dieser Faktoren von n. Angenommen, f sei > sqrt n. Dann ist n/f eine ganze Zahl sqrt n, also kleiner als f. Daher kann f nicht der kleinste Faktor von n sein. Reductio ad absurdum; der kleinste Faktor von n muss sqrt n sein.