wake-up-neo.com

Warum überprüfen wir die Quadratwurzel einer Primzahl, um zu bestimmen, ob es eine Primzahl ist?

Um zu testen, ob eine Zahl Primzahlen ist oder nicht, warum müssen wir testen, ob sie nur bis zur Quadratwurzel dieser Zahl teilbar ist?

303
Pan

Wenn eine Zahl n keine Primzahl ist, kann sie in zwei Faktoren a und b eingeteilt werden:

n = a * b

Wenn sowohl a als auch b größer als die Quadratwurzel von n wären, wäre a * b größer als n. Also muss mindestens einer dieser Faktoren kleiner oder gleich der Quadratwurzel von n sein. Wenn wir keine Faktoren finden können, die kleiner oder gleich der Quadratwurzel sind, muss n eine Primzahl sein.

509
Sven Marnach

Sagen wir m = sqrt(n) dann m × m = n. Wenn nun n keine Primzahl ist, kann n als n = a × b geschrieben werden, also m × m = a × b. Beachten Sie, dass m eine reelle Zahl ist, während n, a und b natürliche Zahlen sind.

Jetzt kann es 3 Fälle geben:

  1. a> m ⇒ b <m
  2. a = m ⇒ b = m
  3. a <m ⇒ b> m

In allen 3 Fällen min(a, b) ≤ m. Wenn wir bis m suchen, müssen wir mindestens einen Faktor von n finden, der ausreicht, um zu zeigen, dass n keine Primzahl ist.

298
BiGYaN

Denn wenn ein Faktor größer als die Quadratwurzel von n ist, ist der andere Faktor, der sich mit n multiplizieren würde, notwendigerweise kleiner als die Quadratwurzel von n.

51
patros

Eine intuitivere Erklärung wäre:

Die Quadratwurzel von 100 ist 10. Sagen wir a x b = 100 für verschiedene Paare von a und b.

Wenn a == b, dann sind sie gleich und genau die Quadratwurzel von 100. Welches ist 10.

Wenn einer von ihnen weniger als 10 ist, muss der andere größer sein. Zum Beispiel 5 x 20 = 100. Einer ist größer als 10, der andere ist kleiner als 10.

Wenn Sie über a x b nachdenken, muss einer der beiden zum Ausgleich größer werden, sodass das Produkt bei 100 bleibt. Sie schwenken um die Quadratwurzel.

Die Quadratwurzel von 101 beträgt ungefähr 10,049875621. Wenn Sie also die Zahl 101 auf Ursprünglichkeit testen, müssen Sie nur die ganzen Zahlen bis 10, einschließlich 10, ausprobieren. Aber 8, 9 und 10 sind nicht selbst Primzahlen, Sie müssen also nur bis 7 testen Prim.

Wenn es ein Paar von Faktoren gibt, bei denen einer der Zahlen größer als 10 ist, muss der andere des Paares kleiner als 10 sein. Wenn der kleinere nicht existiert, gibt es keinen übereinstimmenden größeren Faktor von 101.

Wenn Sie 121 testen, ist die Quadratwurzel 11. Sie müssen die Primzahlen 1 bis 11 (einschließlich) testen, um zu sehen, ob sie gleichmäßig eingehen. 11 geht in 11-mal, also ist 121 keine Primzahl. Wenn Sie bei 10 aufgehört hätten und 11 nicht getestet hätten, hätten Sie 11 verpasst.

Sie müssen jede Primzahl prüfen, die größer als 2 ist, jedoch kleiner oder gleich der Quadratwurzel ist, vorausgesetzt, Sie testen nur ungerade Zahlen.

`

25
Archit Garg

Angenommen, n ist keine Primzahl (größer als 1). Es gibt also Zahlen a und b, so dass

n = ab      (1 < a <= b < n)

Durch Multiplizieren der Beziehung a<=b mit a und b erhalten wir:

a^2 <= ab
 ab <= b^2

Deshalb: (Beachten Sie, dass n=ab)

a^2 <= n <= b^2

Also: (Beachten Sie, dass a und b positiv sind)

a <= sqrt(n) <= b

Wenn also eine Zahl (größer als 1) keine Primzahl ist und wir die Teilbarkeit bis zur Quadratwurzel der Zahl testen, werden wir einen der Faktoren finden.

17
LoMaPh

Nehmen wir an, dass die angegebene ganze Zahl N keine Primzahl ist.

Dann kann N in zwei Faktoren a und b, 2 <= a, b < N eingeteilt werden, so dass N = a*b. Beide können nicht gleichzeitig größer als sqrt(N) sein. 

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

Wenn Sie nun keinen Divisor von N im Bereich [2, sqrt(N)] finden können, was bedeutet das?

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

Daher ist a = 1 und b = n und damit per Definition N prim .

...

Weiter lesen, wenn Sie nicht zufrieden sind:

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

(ein1b1), (ein2b2), (ein3b3), ..... , (einkbk). Nehmen Sie ohne Verlust der Allgemeinheit anich <bich, 1<= i <=k.

Um zeigen zu können, dass N keine Primzahl ist, reicht es aus zu zeigen, dass keines von aich kann weiter faktorisiert werden. Und das wissen wir auch aich <= sqrt(N) und daher müssen Sie prüfen, bis sqrt(N) alle a abdecktich. Und so können Sie feststellen, ob N Primzahl ist oder nicht.

...

6
user8038009

Es ist alles nur eine grundlegende Verwendung von Faktorisierung und Quadratwurzeln.

Es mag abstrakt erscheinen, aber in Wirklichkeit liegt es einfach an der Tatsache, dass die maximal mögliche Fakultät einer Nicht-Primzahl die Quadratwurzel sein müsste, weil:

sqrroot(n) * sqrroot(n) = n.

Wenn eine ganze Zahl über 1 und darunter oder bis zu sqrroot(n) gleichmäßig in n unterteilt wird, kann n keine Primzahl sein.

Pseudocode-Beispiel:

i = 2;

is_prime = true;

while loop (i <= sqrroot(n))
{
  if (n % i == 0)
  {
    is_prime = false;
    exit while;
  }
  ++i;
}
6
Super Cat

Um zu prüfen, ob eine Zahl N Prime ist oder nicht ..__, müssen wir nur prüfen, ob N durch die Zahlen <= SQROOT (N) teilbar ist. Dies liegt daran, dass, wenn wir N in zwei Faktoren einbeziehen, X und Y sagen, dh. N = X Y. Jedes X und Y kann nicht kleiner als SQROOT (N) sein, da dann X Y <N Jedes X und Y kann nicht größer sein als SQROOT (N), weil dann 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 Prime ist, müssen wir nur die Zahlen <= SQROOT (N) prüfen.

4
rhea rodrigues

Nehmen wir an, wir haben eine Zahl "a", die keine Primzahl ist. Eine Zahl, die gleichmäßig durch andere Zahlen als 1 oder sich selbst geteilt werden kann. Zum Beispiel kann 6 durch 2 oder durch 3 sowie durch 1 oder 6] gleichmäßig geteilt werden. 

6 = 1 × 6 oder 6 = 2 × 3

Wenn nun "a" keine Primzahl ist, kann es durch zwei andere Zahlen geteilt werden. Nehmen wir an, diese Zahlen sind "b" und "c". Was bedeutet 

a = b * c.

Wenn nun "b" oder "c", ist einer von ihnen größer als die Quadratwurzel von "a", als die Multiplikation von "b" & "c" größer als "a" ist. 

"B" & "c" ist also immer <= Quadratwurzel von "a", um die Gleichung "a = b * c" zu beweisen.

Wenn wir aus dem oben genannten Grund testen, ob eine Zahl eine Primzahl ist oder nicht, überprüfen wir nur die Quadratwurzel dieser Zahl.

2

Sei n nicht prim. Daher hat es mindestens zwei ganzzahlige Faktoren größer als 1. Sei f der kleinste dieser Faktoren. Angenommen, f> sqrt n. Dann ist n/f eine ganze Zahl LTE 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 LTE sqrt n sein.

1
Reb.Cabin

Wenn eine beliebige Zahl n gegeben ist, können Sie die Faktoren ermitteln, indem Sie die Quadratwurzel p ermitteln:

sqrt(n) = p

Wenn wir p natürlich mit sich selbst multiplizieren, erhalten wir n zurück:

p*p = n

Es kann umgeschrieben werden als:

a*b = n

Wo p = a = b. Wenn a zunimmt, nimmt b ab, um a*b = n zu erhalten. Daher ist p die Obergrenze.

1
typelogic

Um die Primzahl einer Zahl, n, zu testen, würde man eine Schleife wie die folgende erwarten: 

bool isPrime = true;
for(int i = 2; i < n; i++){
    if(n%i == 0){
        isPrime = false;
        break;
    }
}

Was die obige Schleife macht, ist dies: Für ein gegebenes 1 <i <n wird geprüft, ob n/i eine ganze Zahl ist (der Rest bleibt 0). Wenn es ein i gibt, für das n/i eine ganze Zahl ist, können wir sicher sein, dass n keine Primzahl ist. An diesem Punkt endet die Schleife. Wenn für kein i, n/i eine ganze Zahl ist, dann ist n eine Primzahl. 

Wie bei jedem Algorithmus fragen wir: Können wir es besser machen?

Lassen Sie uns sehen, was in der obigen Schleife vor sich geht. 

Die Folge von i lautet: i = 2, 3, 4, ..., n-1

Und die Folge von Ganzzahlprüfungen lautet: j = n/i, das ist n/2, n/3, n/4, ..., n/(n-1) 

Wenn für einige i = a ist n/a eine ganze Zahl, dann ist n/a = k (ganze Zahl)

oder n = ak, klar n> k> 1 (wenn k = 1 ist, dann ist a = n, aber ich erreiche nie n; und wenn k = n ist, dann ist a = 1, aber ich fange von Form 2 an)

Auch ist n/k = a, und wie oben erwähnt, ist a ein Wert von i, so dass n> a> 1 ist. 

A und k sind also ganze Zahlen zwischen 1 und n (exklusiv). Da erreicht i jede ganze Zahl in diesem Bereich, bei einer Iteration i = a und bei einer anderen Iteration i = k. Wenn der Primalitätstest von n für min (a, k) fehlschlägt, schlägt er auch für max (a, k) fehl. Wir müssen also nur einen dieser beiden Fälle prüfen, es sei denn min (a, k) = max (a, k) (wobei zwei Überprüfungen auf einen Wert reduziert werden), dh a = k, an welchem ​​Punkt a * a = n, welcher impliziert a = sqrt (n).

Mit anderen Worten, wenn der Primalitätstest von n für einige i> = sqrt (n) (dh max (a, k)) fehlschlagen würde, würde er auch für einige i <= n (dh min (a k)). Es würde also genügen, wenn wir den Test für i = 2 bis sqrt (n) ausführen.

0
Aroonalok

Jede zusammengesetzte Nummer ist ein Produkt von Primzahlen.

Sagen wir n = p1 * p2, wo p2 > p1 und sie sind Primzahlen.

Wenn n % p1 === 0, ist n eine zusammengesetzte Zahl.

Wenn n % p2 === 0, dann erraten Sie was n % p1 === 0 auch!

Wenn n % p2 === 0 aber n % p1 !== 0 gleichzeitig ist, gibt es keine Möglichkeit. Mit anderen Worten: Wenn eine zusammengesetzte Zahl n gleichmäßig durch p2, p3 ... pi ( sein größerer Faktor) muss auch durch den kleinsten Faktor p1 dividiert werden .. _ Es stellt sich heraus, dass der niedrigste Faktor p1 <= Math.square(n) immer wahr ist.

0
daGo