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

Jede zusammengesetzte Zahl ist ein Produkt von Primzahlen.

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

Si n % p1 === 0 dann n ist eine zusammengesetzte Zahl.

Si n % p2 === 0 dann raten Sie mal n % p1 === 0 auch!

Es gibt also keine Möglichkeit, wenn n % p2 === 0 sondern n % p1 !== 0 zur gleichen Zeit. Mit anderen Worten: Wenn eine zusammengesetzte Zahl n kann gleichmäßig geteilt werden durch p2,p3...pi (sein größerer Faktor) muss durch seinen kleinsten Faktor geteilt werden p1 auch. Es stellt sich heraus, dass der niedrigste Faktor p1 <= Math.square(n) ist immer wahr.

Answer 2

Ja, wie oben richtig erklärt wurde, reicht es aus, bis zu Math.floor der Quadratwurzel einer Zahl zu iterieren, um ihre Primzahl zu prüfen (weil sqrt alle möglichen Fälle von Teilung abdeckt und Math.floor denn jede ganze Zahl über sqrt bereits außerhalb seiner Reichweite).

Hier ist ein lauffähiges JavaScript-Codefragment das eine einfache Implementierung dieses Ansatzes darstellt - und dessen "Laufzeitfreundlichkeit" gut genug ist, um mit ziemlich großen Zahlen umzugehen (ich habe versucht, sowohl Primzahlen als auch Nicht-Primzahlen bis zu 10**12, d.h. 1 Billion, zu überprüfen, und die Ergebnisse mit dem Online-Datenbank der Primzahlen und hatte selbst auf meinem billigen Telefon keine Fehler oder Verzögerungen):

function isPrime(num) {
  if (num % 2 === 0 || num < 3 || !Number.isSafeInteger(num)) {
    return num === 2;
  } else {
    const sqrt = Math.floor(Math.sqrt(num));
    for (let i = 3; i <= sqrt; i += 2) {
      if (num % i === 0) return false;
    }
    return true;
  }
}

<label for="inp">Enter a number and click "Check!":</label><br>
<input type="number" id="inp"></input>
<button onclick="alert(isPrime(+document.getElementById('inp').value) ? 'Prime' : 'Not prime')" type="button">Check!</button>

Answer 3

Um die Primzahl einer Zahl zu prüfen, n würde man in erster Linie eine Schleife wie die folgende erwarten:

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

Die obige Schleife funktioniert folgendermaßen: für eine gegebene 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, dann können wir sicher sein, dass n keine Primzahl ist, und die Schleife endet. 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?

Schauen wir uns an, was in der obigen Schleife vor sich geht.

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

Und die Folge der ganzzahligen Prüfungen lautet: j = n/i, also n/2, n/3, n/4, ... , n/(n-1)

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

oder n = ak, eindeutig n > k > 1 (wenn k = 1, dann a = n, aber i erreicht nie n; und wenn k = n, dann a = 1, aber i beginnt mit 2)

Außerdem ist n/k = a, und wie oben erwähnt, ist a ein Wert von i, also n > a > 1.

a und k sind also beide ganze Zahlen zwischen 1 und n (ausschließlich). Da i jede ganze Zahl in diesem Bereich erreicht, ist bei einer Iteration i = a und bei einer anderen Iteration i = k. Wenn der Primärtest von n für min(a,k) fehlschlägt, wird er auch für max(a,k) fehlschlagen. Wir brauchen also nur einen dieser beiden Fälle zu prüfen, es sei denn, min(a,k) = max(a,k) (dann reduzieren sich zwei Prüfungen auf eine), d.h. a = k , dann ist a*a = n, was a = sqrt(n) impliziert.

Mit anderen Worten: Wenn der Primzahltest von n für einige i >= sqrt(n) (d.h. max(a,k)) fehlschlägt, dann auch für einige i <= n (d.h. min(a,k)). Es würde also genügen, wenn wir den Test für i = 2 bis sqrt(n) durchführen.