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

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

n = a * b

Jetzt a y b kann nicht gleichzeitig größer sein als die Quadratwurzel aus n , da dann das Produkt a * b größer sein würde als sqrt(n) * sqrt(n) = n . In jeder Faktorisierung von n muss mindestens einer der Faktoren kleiner sein als die Quadratwurzel aus n und wenn wir keine Faktoren finden können, die kleiner oder gleich der Quadratwurzel sind, n muss eine Primzahl sein.

Answer 2

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

Nun 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 also suchen bis m finden wir mit Sicherheit mindestens einen Faktor von n was ausreicht, um zu zeigen, dass n nicht primär ist.

Answer 3

Denn wenn ein Faktor größer ist als die Quadratwurzel aus n, ist der andere Faktor, der mit ihm multipliziert werden müsste, um n zu ergeben, notwendigerweise kleiner als die Quadratwurzel aus n.

Answer 4

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

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

Durch Multiplikation der Beziehung a<=b por a y b erhalten wir:

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

Daher: (beachten Sie, dass n=ab )

a^2 <= n <= b^2

Daraus folgt: (Beachten Sie, dass a y 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.

Answer 5

Es handelt sich eigentlich nur um grundlegende Anwendungen 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 ihre Quadratwurzel sein muss, weil:

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

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

Pseudocode-Beispiel:

i = 2;

is_prime = true;

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