Warum tun wir überprüfen, bis auf die Wurzel einer Primzahl zu bestimmen, ob es eine Primzahl ist?

Question

Um zu testen, ob eine Zahl eine Primzahl ist oder nicht, warum tun wir haben, um zu testen, ob es ist teilbar nur bis zur Quadratwurzel der Zahl?

Answer 1

Wenn eine Zahl n ist keine Prime, es kann in zwei Faktoren berücksichtigt werden a und b:

n = a * b

Wenn beides a und b waren größer als die Quadratwurzel von n, dann a * b wäre größer als n. Mindestens einer dieser Faktoren muss also weniger oder gleich der quadratischen Wurzel von sein n, und wenn wir keine Faktoren finden können, die weniger als oder gleich der Quadratwurzel sind, n Muss Prime sein.

Answer 2

Sagen wir m = sqrt(n) dann m × m = n. Nun, wenn n ist damals keine Prime n kann geschrieben werden als n = a × b, Also m × m = a × b. Beachte das m ist eine reelle Zahl, während n, a und b sind natürliche Zahlen.

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. Daher, wenn wir bis nach Tille suchen m, Wir sind verpflichtet, mindestens einen Faktor von zu finden n, was ausreicht, um das zu zeigen n ist nicht primär.

Answer 3

Denn wenn ein Faktor größer als die quadratische Wurzel von n ist, ist der andere Faktor, der sich mit ihm mit n gleich n vervielfachen würde, notwendigerweise geringer als die Quadratwurzel von n.

Answer 4

Eine intuitivere Erklärung wäre:-

Die Quadratwurzel von 100 beträgt 10. Sagen wir AxB = 100 für verschiedene Paare von A und B.

Wenn a == b, dann sind sie gleich und die Quadratwurzel von 100 genau. Das 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 weniger als 10.

Wenn einer von ihnen untergeht, muss der andere an AXB nachdenken, um die Ausgleich zugute zu machen, sodass das Produkt bei 100 bleibt. Sie drehen sich um die Quadratwurzel.

Die Quadratwurzel von 101 beträgt ca. 10,049875621. Wenn Sie also die Nummer 101 für die Primalität testen, müssen Sie die Ganzzahlen nur bis zu 10 ausprobieren, einschließlich 10. Aber 8, 9 und 10 sind nicht selbst Prime, sodass Sie nur bis 7 testen müssen, was ist Prime.

Denn wenn es ein Paar Faktoren mit einer der Zahlen gibt, die größer als 10 sind, muss das andere des Paares weniger als 10 betragen. 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 Prime Ganzzahlen 1 bis 11 (einschließlich) testen, um festzustellen, ob sie gleichmäßig eingeht. 11 geht 11 Mal, also ist 121 nicht primär. Wenn Sie bei 10 angehalten hätten und nicht 11 getestet hätten, hätten Sie 11 verpasst.

Sie müssen jede Prime Ganzzahl von mehr als 2 testen, jedoch weniger als oder gleich der Quadratwurzel, vorausgesetzt, Sie testen nur ungerade Zahlen.

`

Answer 5

Vermuten n ist keine Primzahl (mehr als 1). Es gibt also Zahlen a und b so dass

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

Durch Multiplizieren der Beziehung a<=b durch a und b wir bekommen:

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

Deshalb: (Beachten Sie das n=ab)

a^2 <= n <= b^2

Daher: (Beachten Sie das a und b sind positiv)

a <= sqrt(n) <= b

Wenn also eine Zahl (größer als 1) nicht vorhaben und wir die Spaltbarkeit bis zur Quadratwurzel der Zahl testen, werden wir einen der Faktoren finden.

Answer 6

Es ist alles wirklich grundlegende Verwendungen von Faktorisierung und quadratischen Wurzeln.

Es mag abstrakt zu sein, aber in Wirklichkeit liegt es einfach mit der Tatsache, dass das maximal mögliche Faktor eines Nicht-Abnus-Faktors seine quadratische Wurzel sein müsste, weil:

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

Angesichts dessen, falls eine ganze Zahl oben 1 und unten oder bis zu sqrroot(n) gleichmäßig in n, dann n Kann keine Primzahl sein.

Pseudo-Code-Beispiel:

i = 2;

is_prime = true;

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

Answer 7

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

Dann kann n in zwei Faktoren faktorisiert werden a und b , 2 <= a, b < N so dass N = a*b. Natürlich können beide nicht größer sein als sqrt(N) gleichzeitig.

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

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

Das bedeutet, dass N Hat keinen Teiler in [2, a] wie a <= sqrt(N).

Deswegen, a = 1 und b = n und daher Per Definition, N ist Prime.

...

Weitere Lesen, wenn Sie nicht zufrieden sind:

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

(a₁, b₁), (a₂, b₂), (a₃, b₃), ..... , (a_k, b_k). Ohne Verlust der Allgemeinheit annehmen a_ich <b_ich, 1<= i <=k.

Nun, um das zeigen zu können N Ist es nicht nur ausreichend, um zu zeigen, dass keines von a_ich kann weiter faktorisiert werden. Und wir wissen auch, dass a_ich <= sqrt(N) und so müssen Sie bis nach sehen sqrt(N) die alle a abdecken wird_ich. Und daher können Sie zu dem Schluss kommen, ob oder nicht N ist Prime.

...

Answer 8

Um zu überprüfen, ob eine Nummer n Prime ist oder nicht. Wir müssen nur überprüfen, ob N durch Zahlen <= Sqroot (n) teilbar ist. Dies liegt daran, dass, wenn wir n in 2 Faktoren berücksichtigen, x und y, dh. N = xY. Jedes von x und y kann nicht weniger als Sqroot (n) sein, weil dann xY <n jedes von x und y kann nicht größer sein als Sqroot (n), weil dann x*y> n

Daher muss ein Faktor weniger oder gleich SQROOT (n) sein (während der andere Faktor größer oder gleich SQROOT (n) ist). Um zu überprüfen, ob n Prime ist, müssen wir nur diese Zahlen <= Sqroot (n) überprüfen.

Answer 9

Nehmen wir an, wir haben eine Zahl "A", die nicht Primes [nicht Prim-/Composite -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 3 sowie durch 1 oder 6 geteilt werden].

6 = 1 × 6 oder 6 = 2 × 3

Wenn also "a" nicht primär ist, kann es durch zwei andere Zahlen geteilt werden und sagen wir, diese Zahlen sind "B" und "C". Was bedeutet

a = b*c.

Wenn "B" oder "C" nun, ist jeder von ihnen größer als die Quadratwurzel von "A" als Multiplikation von "B" & "C" ist größer als "A".

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

Aufgrund des oben genannten Grundes prüfen wir, ob eine Zahl für eine Zahl ist oder nicht, nur bis zur Quadratwurzel dieser Zahl.

Answer 10

Sei n nicht prim. Daher hat es mindestens zwei ganzzahlige Faktoren, die größer als 1 sind. Sei F die kleinsten von Ns solchen Faktoren. Angenommen, f> sqrt n. Dann ist N/F eine Ganzzahl lte Sqrt n, also kleiner als F. Daher kann F nicht der kleinste Faktor von N sein. Reduktion ad absurdum; Ns kleinster Faktor muss lte sqrt n sein.

Answer 11

Gegebenenfalls eine beliebige Zahl n, Ein Weg, seine Faktoren zu finden, besteht darin, seine Quadratwurzel zu erhalten p:

sqrt(n) = p

Natürlich, wenn wir uns multiplizieren p Dann kommen wir zurück n:

p*p = n

Es kann erneut geschrieben werden wie:

a*b = n

Wo p = a = b. Wenn a erhöht sich dann b abnimmt zu warten a*b = n. Deswegen, p ist die Obergrenze.

Answer 12

Testen Sie die primality of a number, n, würde man erwarten , eine Schleife wie der folgenden in Erster Linie :

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

Was die obige Schleife tut, ist dies :für eine gegebene 1 < ich < n, es prüft, ob n/i ist ein integer-Wert (Blätter Rest 0).Wenn es existiert ein i n/i ist eine ganze Zahl, dann können wir sicher sein, dass n keine Primzahl ist, an welcher Stelle die Schleife beendet.Wenn aus keinem i, n/i ist eine ganze Zahl, dann ist n eine Primzahl ist.

Wie bei jedem Algorithmus, bitten wir : Können wir besser machen ?

Lassen Sie uns sehen, was Los ist in der obigen Schleife.

Die Reihenfolge von i gilt :i = 2, 3, 4, ..., n-1

Und die Sequenz von integer-Prüfungen geht :j = n/i, die n/2, n/3, n/4, ... n/(n-1)

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

oder n = ak, klar n > k > 1 (falls k = 1, dann a = n, aber ich habe es nie erreicht, n;und wenn k = n, dann ist a = 1, aber ich beginnt, form 2)

Auch, n/k = a, und, wie oben angegeben, ein Wert von i, so dass n > a > 1.

Also, a und k sind die beiden ganzen zahlen zwischen 1 und n (exklusive).Da ich es erreicht jeden ganzzahligen Wert in diesem Bereich auf einige iteration i = a, und bei einigen anderen iteration i = k.Wenn die primality test von n fehl min(a,k), es wird auch nicht für max(a,k).Also müssen wir schauen nur einer dieser beiden Fälle, es sei denn, min(a,k) = max(a,k) (wo zwei überprüfungen reduzieren, um eine), d.h., a = k , an welcher Stelle a*a = n, und das bedeutet a = sqrt(n).

In anderen Worten, wenn die primality test von n waren, um Fehler für einige i >= sqrt(n) (d.h., max(a,k)), dann es würde auch nicht für einige habe ich <= n (d.h., min(a,k)).Also, es würde genügen, wenn wir den test ausführen, für i = 2 to sqrt(n).

Answer 13

Jede Verbundzahl ist ein Produkt von Primzahlen.

Nehmen wir mal an n = p1 * p2, wo p2 > p1 Und sie sind Primzahlen.

Wenn n % p1 === 0 dann n ist eine zusammengesetzte Nummer.

Wenn n % p2 === 0 Dann raten Sie mal was n % p1 === 0 auch!

Es gibt also keine Möglichkeit, wenn n % p2 === 0 aber n % p1 !== 0 zur selben Zeit. Mit anderen Worten, wenn eine zusammengesetzte Nummer n kann gleichmäßig durch geteilt werden durchp2, p3 ... pi (sein größerer Faktor) muss durch seinen niedrigsten Faktor geteilt werden P1 zu. Es stellt sich heraus, dass der niedrigste Faktor p1 <= Math.square(n) ist immer wahr.