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 ?
Si un nombre n n'est pas un nombre premier, il peut être décomposé en deux facteurs a y b :
n = a * bMaintenant a y b ne peut pas être à la fois plus grande que la racine carrée de n car alors le produit a * b serait supérieure à sqrt(n) * sqrt(n) = n . Ainsi, dans toute factorisation de n au moins un des facteurs doit être inférieur à la racine carrée de n et si nous ne trouvons aucun facteur inférieur ou égal à la racine carrée, n doit être un nombre premier.
Comment sqrt(n) doivent être suffisamment précises pour que cette propriété soit respectée, étant donné que nous utilisons des points flottants.
@Benoît Vous pouvez toujours utiliser le chèque. i * i <= n au lieu de i <= sqrt(n) si vous voulez éviter les subtilités des nombres à virgule flottante.
Puisque ce n'est pas le cas blesser (sauf parfois une division supplémentaire) pour vérifier un diviseur de plus, vous pouvez simplement calculer ceil(sqrt(n)).
Disons que m = sqrt(n) puis m × m = n . Maintenant si n n'est pas un nombre premier, alors n peut s'écrire comme suit n = a × b donc m × m = a × b . Remarquez que m est un nombre réel alors que n , a y b sont des nombres naturels.
Maintenant, il peut y avoir 3 cas :
Dans les 3 cas, min(a, b) m . Donc si on cherche jusqu'à m nous sommes sûrs de trouver au moins un facteur de n ce qui suffit à montrer que n n'est pas premier.
N = 12 m = sqrt(12) = 3,46, a = 2, b = 6. n = m m c'est-à-dire 12=3,46*3,46 et n = a b c'est-à-dire 12=2*6. Maintenant condition 3. a < m < b c'est à dire 2 < 3.46 < 6. Donc pour vérifier le nombre premier, il suffit de vérifier le nombre inférieur à 3,46 qui est 2 pour découvrir que le nombre n'est pas premier. Donc, vérifier la divisibilité par des nombres inférieurs ou égaux à (si n = 4, m=a=b=2) la racine carrée de n.
Je pense que nous devrions d'abord souligner l'hypothèse. Supposons que n is not a prime et le prouver, sinon c'est un premier.
En fait, je ne suis pas convaincu que ce soit une meilleure réponse. C'est une réponse correcte, mais elle ne répond pas vraiment à la question. Elle décrit simplement d'autres dynamiques autour des nombres premiers et du sqrt. La réponse de @Sven est à la fois succincte et ne crée pas plus de questions dans le processus.
Une explication plus intuitive serait :-
La racine carrée de 100 est 10. Disons que 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. Ce qui donne 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.
Si l'on considère le rapport a x b, si l'un d'eux diminue, l'autre doit augmenter pour compenser, de sorte que le produit reste égal à 100. Ils pivotent autour de la racine carrée.
La racine carrée de 101 est d'environ 10,049875621. Donc, si vous testez la primalité du nombre 101, vous n'avez besoin d'essayer que les entiers jusqu'à 10, y compris 10. Mais 8, 9 et 10 ne sont pas des nombres premiers, donc vous ne devez tester que les nombres jusqu'à 7, qui est premier.
Parce que s'il y a une paire de facteurs dont l'un des nombres est 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 tu testes 121, la racine carrée est 11. Vous devez tester les nombres entiers premiers de 1 à 11 (inclus) pour voir s'ils sont égaux. 11 entre 11 fois, donc 121 n'est pas premier. Si vous vous étiez arrêté à 10, sans tester 11, vous auriez manqué 11.
Vous devez tester chaque nombre entier premier supérieur à 2, mais inférieur ou égal à la racine carrée, en supposant que vous ne testez que les nombres impairs.
`
Supposons que n n'est pas un nombre premier (supérieur à 1). Il existe donc des nombres a y b de telle sorte que
n = ab (1 < a <= b < n)En multipliant la relation a<=b par a y b on obtient :
a^2 <= ab
ab <= b^2Par conséquent : (notez que n=ab )
a^2 <= n <= b^2D'où : (Notez que a y b sont positifs)
a <= sqrt(n) <= bAinsi, 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.
Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.
53 votes
Car si
n = a*bya <= bpuisa*a <= a*b = n.18 votes
Pour clarifier, cela signifie que nous devons tester uniquement jusqu'à ce que
floor(sqrt(n)).7 votes
mathandmultimedia.com/2012/06/02/