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

393

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

La poêle
la source
33
parce que si n = a*bet a <= balors a*a <= a*b = n.
Will Ness
7
Pour clarifier, cela signifie que nous devons tester uniquement jusqu'à floor(sqrt(n)).
Acumenus

Réponses:

660

Si un nombre nn'est pas un nombre premier, il peut être divisé en deux facteurs aet b:

n = a * b

Maintenant aet bne peut pas être à la fois supérieur à la racine carrée de n, car alors le produit a * bserait supérieur à sqrt(n) * sqrt(n) = n. Donc, dans toute factorisation de n, au moins un des facteurs doit être inférieur à la racine carrée de n, et si nous ne pouvons trouver aucun facteur inférieur ou égal à la racine carrée, ndoit être un nombre premier.

Sven Marnach
la source
Comment doit sqrt(n)-il être suffisamment précis pour que cette propriété soit valable étant donné que nous utilisons des virgules flottantes.
Benoît
@ Benoît Vous pouvez toujours utiliser la vérification i * i <= nau lieu de i <= sqrt(n)si vous voulez éviter les subtilités des nombres à virgule flottante.
Sven Marnach
348

Disons m = sqrt(n)alors m × m = n. Maintenant, si ce nn'est pas un nombre premier, alors non peut l'écrire n = a × bainsi m × m = a × b. Notez que mc'est un nombre réel alors que n, aet bsont des nombres naturels.

Maintenant, il peut y avoir 3 cas:

  1. a> m ⇒ b <m
  2. a = m ⇒ b = m
  3. a <m ⇒ b> m

Dans les 3 cas, min(a, b) ≤ m. Par conséquent, si nous recherchons jusqu'à m, nous sommes tenus de trouver au moins un facteur de n, ce qui suffit pour montrer que ce nn'est pas un facteur premier.

BiGYaN
la source
4
n = 12 m = sqrt (12) = 3,46, a = 2, b = 6. n = m m soit 12 = 3,46 * 3,46 et n = a b soit 12 = 2 * 6. Maintenant, condition 3. a <m <b, c'est-à-dire 2 <3,46 <6. Donc, pour vérifier le nombre premier, il nous suffit de vérifier le nombre inférieur à 3,46 qui est 2 pour savoir que ce nombre n'est pas premier. Par conséquent, vérifiez la divisibilité par des nombres inférieurs ou égaux (si n = 4, m = a = b = 2) à la racine carrée de n.
anukalp
2
Je pense que nous devons d'abord souligner l'hypothèse. Supposons n is not a prime, et le prouvons, sinon c'est un premier choix.
Huei Tan
En fait, je ne suis pas convaincu que ce soit une meilleure réponse. C'est une bonne réponse, mais cela ne répond pas vraiment à la question. Il décrit simplement quelques autres dynamiques autour des nombres premiers et du sqrt. @ Les réponses de Sven sont à la fois succinctes et ne créent pas plus de questions dans le processus.
Jon M
1
Je suis revenu à la dernière bonne version. vous l'avez manqué quand quelqu'un a supprimé inutilement un mot («d'où»), qui est nécessaire pour le flux.
Will Ness le
55

Parce que si un facteur est supérieur à la racine carrée de n, l'autre facteur qui se multiplierait avec lui pour égaler n est nécessairement inférieur à la racine carrée de n.

patros
la source
37

Une explication plus intuitive serait: -

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

Si a == b, alors ils sont égaux et sont exactement la racine carrée de 100. Ce qui est 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 à axb, si l'un d'eux descend, l'autre doit devenir plus gros pour compenser, de sorte que 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 primauté, vous n'avez qu'à essayer les entiers jusqu'à 10, y compris 10. Mais 8, 9 et 10 ne sont pas eux-mêmes premiers, vous n'avez donc qu'à tester jusqu'à 7, ce qui est premier.

Parce que s'il y a une paire de facteurs avec l'un des nombres supérieur à 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 plus grand correspondant de 101.

Si vous testez 121, la racine carrée est 11. Vous devez tester les entiers premiers de 1 à 11 (inclus) pour voir s'ils entrent uniformément. 11 va en 11 fois, donc 121 n'est pas premier. Si vous vous étiez arrêté à 10 ans et que vous n'aviez pas testé 11, vous en 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 testez uniquement des nombres impairs.

"

Archit Garg
la source
3
"En pensant à axb, si l'un d'entre eux descend, l'autre doit devenir plus gros pour compenser, de sorte que le produit reste à 100. Ils pivotent autour de la racine carrée." Mon moment aha! Je vous remercie!
Brian Wigginton
C'est la meilleure réponse.
JeanieJ
19

Supposons que ce nne soit pas un nombre premier (supérieur à 1). Il y a donc des chiffres aet btels que

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

En multipliant la relation a<=b par aet bon 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 bsont 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.

LoMaPh
la source
8

Supposons que l'entier donné N ne soit pas premier,

Alors N peut être factorisé en deux facteurs aet b, 2 <= a, b < Ntels que N = a*b. De toute évidence, les deux ne peuvent pas être plus grands que sqrt(N)simultanément.

Supposons sans perte de généralité aplus petite.

Maintenant, si vous ne pouviez pas trouver de diviseur d' Nappartenance à la gamme [2, sqrt(N)], qu'est-ce que cela signifie?

Cela signifie qu'il Nn'a pas de diviseur dans[2, a] tant que a <= sqrt(N).

Par conséquent, a = 1et b = ndonc par définition, Nest premier .

...

Lectures complémentaires si vous n'êtes pas satisfait:

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

(a 1 , b 1 ), (a 2 , b 2 ), (a 3 , b 3 ), ....., (a k , b k ). Sans perte de généralité, supposons a i <b i ,1<= i <=k .

Maintenant, pour pouvoir montrer que ce Nn'est pas premier, il suffit de montrer qu'aucun des i ne peut être factorisé davantage. Et nous savons également que a i <= sqrt(N)et donc vous devez vérifier jusqu'à sqrt(N)ce qui couvrira tout a i . Et par conséquent, vous pourrez conclure si oui ou non Nest premier.

...


la source
7

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

Cela peut sembler abstrait, mais en réalité, cela tient simplement au 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 supérieur 1et inférieur ou supérieur à se sqrroot(n)divise également en n,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;
}
Super Cat
la source
Observation brillante. Utiliser cette observation pour créer une guarddéclaration dans Swift en conjonction avec ce stackoverflow.com/a/25555762/4475605 pratique pour effectuer une sortie anticipée d'un calcul plutôt que de gaspiller de la puissance de calcul. Merci d'avoir posté.
Adrian
@Adrian Je dois avouer qu'après être revenu à cette réponse, j'ai trouvé une erreur au moment de votre publication. Vous ne pouvez pas effectuer de division sur un 0, et en théorie si vous le pouviez++i devenir le numéro 1, ce qui retournerait toujours faux (parce que 1 se divise en tout). J'ai corrigé la réponse ci-dessus.
Super Cat
Oui ... J'ai abordé cela dans mon code ... votre observation de racine carrée est un excellent moyen de jeter une valeur non prime tôt avant de commencer à exécuter des calculs. Je me faisais tuer sur un grand nombre qui s'est avéré être une grosse perte de temps. J'ai également appris que cet algorithme peut également réduire considérablement les temps de traitement sur les grands nombres. en.wikipedia.org/wiki/Miller –Rabin_primality_test
Adrian
6

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, disons X et Y, c'est-à-dire. 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 pas ê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)). Donc, pour vérifier si N est premier, nous devons seulement vérifier ces nombres <= SQROOT (N).

nandou rodrigues
la source
3

Disons que nous avons un nombre "a", qui n'est pas un nombre premier [pas un nombre premier / composé signifie - un nombre qui peut être divisé également 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

Alors maintenant, si "a" n'est pas premier, 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" & "c" sera supérieure à "a".

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

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

Abu Naser Md Shoaib
la source
1
b & c <= Math.sqrt (n) ?; Ce devrait être plutôt b || c (b ou c) puisque si n = 6, b = 3, c = 2 alors Math.sqrt (n)> c.
daGo
Merci mon pote pour la correction. faire la correction. :)
Abu Naser Md Shoaib
2

É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 on se multiplie ppar lui-même, on revient n:

p*p = n

Il peut être réécrit comme:

a*b = n

O p = a = b.. Si aaugmente, puis bdiminue pour se maintenir a*b = n. C'est donc pla limite supérieure.

Mise à jour: je relis cette réponse encore aujourd'hui et elle est devenue plus claire pour moi. La valeur pne signifie pas nécessairement un entier parce que si c'est le cas, alors nce ne serait pas un nombre premier. Donc, ppourrait être un nombre réel (c'est-à-dire avec des fractions). Et au lieu de parcourir toute la gamme de n, il ne nous reste plus qu'à parcourir toute la gamme de p. L'autre pest une copie miroir, donc nous réduisons la plage de moitié. Et puis, maintenant je vois que nous pouvons réellement continuer à refaire le square rootet à le faire pà plus de la moitié de la plage.

truthadjustr
la source
1

Soit n un nombre non premier. Par conséquent, il a au moins deux facteurs entiers supérieurs à 1. Soit f le plus petit de n de tels facteurs. 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.

Reb.Cabin
la source
1

Tout nombre composite est un produit de nombres premiers.

Disons n = p1 * p2, où p2 > p1et ce sont des nombres premiers.

Si n % p1 === 0alors n est un nombre composite.

Si n % p2 === 0alors devinez quoi n % p1 === 0aussi!

Il n'y a donc aucun moyen que si n % p2 === 0mais n % p1 !== 0en même temps. En d'autres termes, si un nombre composé n peut être divisé également par p2, p3 ... pi (son plus grand facteur), il doit également être divisé par son plus petit facteur p1 . Il s'avère que le facteur le plus bas p1 <= Math.square(n)est toujours vrai.

daGo
la source
Si vous êtes curieux de savoir pourquoi il est vrai, @LoMaPh a grandement expliqué le fait dans sa réponse. J'ai ajouté ma réponse parce que j'avais vraiment du mal à visualiser et à comprendre les autres réponses fournies. Il n'a tout simplement pas cliqué.
daGo
0

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

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

Voici ce que fait la boucle ci-dessus: pour un 1 <i <n donné , elle 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ûrs que n n'est pas un nombre premier, auquel point la boucle se termine. Si pour non 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 i = 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 i n'atteint jamais n; et si k = n, alors a = 1, mais i commence la forme 2)

De plus, n / k = a, et comme indiqué ci-dessus, a est une valeur de i donc n> a> 1.

Ainsi, a et k sont tous deux des entiers compris entre 1 et n (exclusif). Depuis, i atteint chaque entier de cette plage, à une certaine 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, auquel point a * a = n, qui implique a = sqrt (n).

En d'autres termes, si le test de primalité de n échouait pour certains i> = sqrt (n) (c.-à-d. Max (a, k)), il échouerait également pour certains i <= n (c.-à-d. Min (a , k)). Donc, il suffirait d'exécuter le test pour i = 2 à sqrt (n).

Aroonalok
la source
Il y a beaucoup plus court et à mon humble avis beaucoup plus facile à comprendre et plus d'explications sur le sujet dans les commentaires et les réponses de 6 ans ...
Thierry Lathuille