Pourquoi vérifie-t-on jusqu'à la racine carrée d'un nombre premier pour déterminer s'il est premier ?

Question

Pour vérifier si un nombre est premier ou non, pourquoi devons-nous vérifier s'il est divisible uniquement jusqu'à la racine carrée de ce nombre ?

Answer 1

Ce ne sont que des utilisations basiques de la factorisation et des racines carrées.

Cela peut sembler abstrait, mais en réalité, il s'agit simplement du fait que la factorielle maximale possible d'un nombre non primaire doit être sa racine carrée :

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

Étant donné que, si un nombre entier supérieur à 1 et en dessous ou jusqu'à sqrroot(n) div div div div div div div div div div div div div div div div div div div div div div div div div div div div div n entonces n ne peut pas être un nombre premier.

Exemple de pseudo-code :

i = 2;

is_prime = true;

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

Answer 2

Supposons que l'entier donné N n'est pas premier,

Alors N peut être factorisé en deux facteurs a y b , 2 <= a, b < N tal que N = a*b . Il est clair que les deux ne peuvent pas être supérieurs à sqrt(N) simultanément.

Supposons, sans perte de généralité, que a est plus petit.

Maintenant, si vous ne pouviez pas trouver un diviseur de N appartenant à la gamme [2, sqrt(N)] Qu'est-ce que ça veut dire ?

Cela signifie que N [2, a] como a <= sqrt(N) .

Par conséquent, a = 1 y b = n et donc Par définition, N est premier .

...

Une lecture plus approfondie si vous n'êtes pas satisfait :

De nombreuses combinaisons différentes de (a, b) peuvent être possibles. Disons qu'ils le sont :

(a ₁ , b ₁ ), (a ₂ , b ₂ ), (a ₃ , b ₃ ), ..... , (a _k , b _k ). Sans perte de généralité, supposons que a _i < b _i , 1<= i <=k .

Maintenant, pour être capable de montrer que N n'est pas premier, il suffit de montrer qu'aucun de a _i peut être factorisé davantage. Et nous savons aussi qu'un _i <= sqrt(N) et donc vous devez vérifier jusqu'à sqrt(N) qui couvrira tous les a _i . Et donc vous serez en mesure de conclure si oui ou non N est premier.

...

Answer 3

Donc pour vérifier si un nombre N est premier ou non. Nous devons seulement vérifier si N est divisible par des nombres<=SQROOT(N). En effet, si nous factorisons N en 2 facteurs quelconques, disons X et Y, c'est-à-dire que N=X Y. Chacun de X et Y ne peut pas être inférieur à SQROOT(N) car alors, X Y < N Chacun de X et Y ne peut être supérieur à SQROOT(N) car alors, X*Y > N

Par conséquent, un facteur doit être inférieur ou égal à SQROOT(N) ( tandis que l'autre facteur est supérieur ou égal à SQROOT(N) ). Ainsi, pour vérifier si N est premier, il suffit de vérifier les nombres <= SQROOT(N).

Answer 4

Disons que nous avons un nombre "a", qui n'est pas premier [un nombre non premier/composé signifie - un nombre qui peut être divisé de manière égale par des nombres autres que 1 ou lui-même. Par exemple, 6 peut être divisé également par 2, ou par 3, ainsi que par 1 ou 6].

6 = 1 × 6 ou 6 = 2 × 3

Donc maintenant, si "a" n'est pas premier, alors il peut être divisé par deux autres nombres et disons que ces nombres sont "b" et "c". Ce qui signifie

a=b*c.

Maintenant, si "b" ou "c", l'un d'entre eux est supérieur à la racine carrée de "a", alors la multiplication de "b" et "c" sera supérieure à "a".

Ainsi, "b" ou "c" est toujours <= racine carrée de "a" pour prouver l'équation "a=b*c".

Pour cette raison, lorsque nous testons si un nombre est premier ou non, nous ne vérifions que la racine carrée de ce nombre.

Answer 5

Étant donné un nombre quelconque n alors une façon de trouver ses facteurs est d'obtenir sa racine carrée. p :

sqrt(n) = p

Bien sûr, si on multiplie p par lui-même, alors on obtient n :

p*p = n

On peut le réécrire comme suit :

a*b = n

Où p = a = b . Si a augmente, alors b diminue pour maintenir a*b = n . Par conséquent, p est la limite supérieure.

Mise à jour : Je relis cette réponse aujourd'hui et elle est devenue plus claire pour moi. La valeur p ne signifie pas nécessairement un nombre entier, car si c'est le cas, alors n ne serait pas une prime. Donc, p pourrait être un nombre réel (c'est-à-dire avec des fractions). Et au lieu de parcourir toute la gamme des n il ne nous reste plus qu'à parcourir toute la gamme de p . L'autre p est une copie miroir, donc en fait, nous divisons la gamme par deux. Et puis, maintenant je vois que nous pouvons en fait continuer à refaire la square root et de le faire à p pour réduire encore de moitié la portée.