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

, disons m = sqrt(n), puis m × m = n. Maintenant, si n n'est pas un nombre premier alors n peut être écrite sous la forme n = a × b, donc m × m = a × b. Notez que m est un nombre réel, alors que n, a et b sont des nombres naturels.

Maintenant, il peut y avoir 3 Cas:

1. a > M ⇒ b
2. a = M ⇒ b = M
3. a M

Dans les 3 Cas, min(a, b) ≤ m. Par conséquent, si l'on recherche jusqu' m, nous avons l'obligation de trouver au moins un facteur de n, ce qui est suffisant pour montrer que n n'est pas premier.

, Car si un facteur est plus grand que la racine carrée de n, l'autre facteur qui pourrait multiplier à l'égalité n est nécessairement inférieur à la racine carrée de n.

Une explication plus intuitive serait : -

La racine carrée de 100 est 10. Disons A X b = 100, pour différentes paires de a et B.

Si a = = b, alors ils sont égaux, et sont la racine carrée de 100, exactement. Soit 10.

Si l'un d'eux est inférieur à 10, l'autre doit être supérieur. Par exemple, 5 x 20 == 100. L'un est supérieur à 10, l'autre est inférieur à 10.

En pensant à un X b, si l'un d'eux descend, l'autre doit grossir pour compenser, donc le le produit reste à 100. Ils pivotent autour de la racine carrée.

La racine carrée de 101 est d'environ 10.049875621. Donc, si vous testez le nombre 101 pour la primalité, il vous suffit d'essayer les entiers jusqu'à 10, y compris 10. Mais 8, 9 et 10 ne sont pas eux-mêmes premiers, donc vous n'avez qu'à tester jusqu'à 7, qui est premier.

Parce que si il ya une paire de facteurs dont l'un des nombres supérieurs à 10, l'autre de la paire doit être inférieur à 10. Si le plus petit n'existe pas, il n'y a pas de facteur correspondant plus grand de 101.

Si vous testez 121, la racine carrée est 11. Vous devez tester les entiers premiers 1 à 11 (inclus) pour voir si cela va uniformément. 11 va dans 11 fois, donc 121 n'est pas premier. Si vous aviez arrêté à 10, et non testé 11, vous auriez manqué 11.

Vous devez tester chaque entier premier supérieur à 2, mais inférieur ou égal à la racine carrée, en supposant que vous ne testez que des nombres impairs.

`

Supposons que n n'est pas un nombre premier (supérieur à 1). Il y a donc des nombres a et b tels que

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

En multipliant la relation a<=b par a et b on obtient:

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

Par conséquent: (notez que n=ab)

a^2 <= n <= b^2

Par conséquent: (notez que a et b sont positifs)

a <= sqrt(n) <= b

Donc, si un nombre (supérieur à 1) n'est pas premier et que nous testons la divisibilité jusqu'à la racine carrée du nombre, nous trouverons l'un des facteurs.

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

, Alors N peut être factorisée en deux facteurs a et b , 2 <= a, b < N tel que N = a*b. De toute évidence, les deux ne peuvent pas être supérieurs à sqrt(N) simultanément.

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

Maintenant, si vous ne trouvez aucun diviseur de N appartenant à la plage [2, sqrt(N)], qu'est-ce que cela signifie?

Cela signifie que N n'a pas de diviseur de [2, a] comme a <= sqrt(N).

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

...

Pour Plus d'informations si vous n'êtes pas satisfait:

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

(un₁, b₁), (un₂, b₂), (un₃, b₃), ..... (a_k, b_k). Sans perte de généralité, supposons un _ije, 1<= i <=k.

Maintenant, pour être en mesure de montrer que N n'est pas premier, il suffit de montrer qu'aucun de_{, je} peut être factorisée plus loin. Et nous savons aussi qu'un_jesqrt(N) et donc vous avez besoin de vérifier jusqu'à sqrt(N), qui couvrira tous un_{, je}. Et par conséquent, vous serez en mesure de conclure si oui ou non N est premier.

...

Ce ne sont que des utilisations de base de la factorisation et des Racines Carrées.

Il peut sembler abstrait, mais en réalité il réside simplement dans le fait que la factorielle maximale possible d'un nombre Non-premier devrait être sa racine carrée parce que:

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

, étant Donné que, si un nombre entier au-dessus de 1 et ci-dessous ou jusqu'à sqrroot(n) divise de manière égale n, alors n ne peut pas être un nombre premier.

Pseudo-code exemple:

i = 2;

is_prime = true;

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

Donc pour vérifier si un nombre N est Premier ou non. Nous devons seulement vérifier si N est divisible par des nombresY. Chacun de X et Y ne peut pas être infé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)). Donc, pour vérifier si N est Premier nous devons seulement vérifier ces nombres

Disons que nous avons un nombre "a", qui n'est pas premier [pas un nombre premier/composite signifie - un nombre qui peut être divisé uniformément par des nombres autres que 1 ou lui-même. Par exemple, 6 peut être divisée de manière égale 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'eux est supérieur à la racine carrée de " a "que la multiplication de" b "et" c "sera supérieure à"a".

Donc, "b" et "c" est toujours

En raison de la raison ci-dessus, lorsque nous testons si un nombre est Premier ou non, nous vérifions seulement jusqu'à la racine carrée de ce nombre.

, soit n non premier. Par conséquent, il a au moins deux facteurs entiers supérieurs à 1. Soit f le plus petit de ces facteurs de N. Supposons que f > sqrt N. alors n / f est un entier LTE sqrt N, donc plus petit que f. Par conséquent, f ne peut pas être le plus petit facteur de N. Reductio ad absurdum; le plus petit facteur de n doit être LTE sqrt n.

Pour tester la primalité d'un nombre, n , on s'attendrait à une boucle telle que suivante en premier lieu:

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

Ce Que fait la boucle ci-dessus est la suivante : pour un 1 donné, il vérifie si n/i est un entier (laisse le reste 0). S'il existe un i pour lequel n/i est un entier, alors nous pouvons être sûr que ce n est pas un nombre premier, à quel point la boucle se termine. Si ce n'est pour i, n/i est un entier, alors n est premier.

Comme pour tout algorithme, nous demandons : Pouvons-nous faire mieux ?

Voyons ce qui se passe dans la boucle ci-dessus.

La séquence de i va: i = 2, 3, 4,... n-1

Et la séquence de contrôles entiers va: j = n/i, qui est n/2, n/3, N / 4, ... , n / (n-1)

Si pour certains, j'ai = a, n/a est un entier, alors n/a = k (entier)

Ou n = ak, clairement n > k > 1 (si k = 1, alors a = n, mais je n'ai jamais atteint le n; et, si k = n, alors a = 1, mais je commence formulaire 2)

Aussi, n / k = a, et comme indiqué ci-dessus, a est une valeur de I so N > a > 1.

Donc, a et k sont tous deux des entiers compris entre 1 et n (exclusif). Puisque, i atteint chaque entier dans cette plage, à une itération i = a, et à une autre itération i = k. si le test de primalité de n échoue pour min (A, k), il échouera également pour max(A, k). Nous devons donc vérifier un seul de ces deux cas, à moins que min (A, k) = max (a, k) (où deux contrôles se réduisent à un) c'est-à-dire a = k , à quel point A*A = n, ce qui implique A = sqrt(n).

En d'autres termes, si le test de primalité de n devait échouer pour certains i > = sqrt (n) (c'est-à-dire, max (A, k)), alors il échouerait également pour certains i

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

sqrt(n) = p

Bien sûr, si nous multiplions p par lui-même, puis nous revenons n:

p*p = n

Il peut être réécrit comme:

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.