Alors, laissez-moi vous raconter une petite histoire. Un jour, j'étais chez ma grand-mère, et elle essayait de partager des macarons équitablement entre ses petits-enfants. (Oui, j'ai une grand-mère très chic.) Le problème, c'est qu'elle n'arrivait jamais à les partager sans qu'il en reste un ou deux! Elle s'est exclamée: "Oh, ces nombres premiers, ils me donnent du fil à retordre!" Et c'est là que je me suis dit: "Tiens, les nombres premiers, c'est vrai que c'est pas toujours évident de savoir si un nombre en est un!"
Ça vous est déjà arrivé, non? De vous demander si un nombre est premier, et de ne pas savoir par où commencer? Pas de panique! On va décortiquer ça ensemble, sans se prendre la tête.
C'est quoi, un nombre premier, au juste?
Bon, pour ceux qui auraient séché les cours de maths (ça arrive, hein? ;)), rappelons les bases: un nombre premier, c'est un nombre entier supérieur à 1 qui n'est divisible que par 1 et par lui-même. Point barre. Pas de triche!
Par exemple:
- 2 est premier (divisible par 1 et 2)
- 3 est premier (divisible par 1 et 3)
- 5 est premier (divisible par 1 et 5)
- 7 est premier (divisible par 1 et 7)
- MAIS 4 n'est PAS premier (divisible par 1, 2 et 4)
Simple, non? Enfin, simple... Jusqu'à un certain point. Parce que pour les petits nombres, c'est facile de vérifier. Mais quand on commence à parler de nombres à 5, 6, voire 10 chiffres, ça se complique sérieusement.
Les méthodes (plus ou moins) efficaces pour tester la primalité
Alors, comment on fait pour savoir si un nombre est premier quand on n'a pas envie de passer sa vie à faire des divisions à la main? (Soyons honnêtes, personne n'a envie de ça.)
La méthode "bourrin" (mais qui marche)
C'est la méthode la plus simple à comprendre, mais aussi la plus lente. Le principe est simple: on teste si le nombre est divisible par tous les nombres entiers inférieurs à lui (en commençant par 2). Si aucun ne le divise, c'est qu'il est premier! (Attention, on exclut 1 évidemment, parce que tout est divisible par 1...)
Prenons l'exemple de 13:
- 13 / 2 = 6.5 (pas entier)
- 13 / 3 = 4.333... (pas entier)
- 13 / 4 = 3.25 (pas entier)
- 13 / 5 = 2.6 (pas entier)
- 13 / 6 = 2.166... (pas entier)
- 13 / 7 = 1.857... (pas entier)
- 13 / 8 = 1.625 (pas entier)
- 13 / 9 = 1.444... (pas entier)
- 13 / 10 = 1.3 (pas entier)
- 13 / 11 = 1.181... (pas entier)
- 13 / 12 = 1.083... (pas entier)
Conclusion: 13 est bien un nombre premier!
Bon, vous voyez le problème, non? Pour un nombre comme 1000000007 (qui est, au passage, un nombre premier très utilisé en informatique), il faudrait tester énormément de diviseurs! C'est un peu longuet...
L'optimisation qui change la vie: la racine carrée
Voici une astuce qui va vous faire gagner un temps précieux: on n'a pas besoin de tester tous les nombres jusqu'à n, mais seulement jusqu'à la racine carrée de n. Oui, vous avez bien lu!
Pourquoi? Parce que si n a un diviseur plus grand que sa racine carrée, alors il a forcément un autre diviseur plus petit que sa racine carrée. (Réfléchissez-y quelques secondes, ça a du sens, non?)
Exemple avec 13, toujours:
- La racine carrée de 13 est environ 3.6.
- On teste donc seulement 2 et 3.
- 13 / 2 = 6.5 (pas entier)
- 13 / 3 = 4.333... (pas entier)
Et voilà! Beaucoup plus rapide, non?
Concrètement, en Python, ça donne un code du genre:
import math
def est_premier(n):
if n <= 1:
return False
for i in range(2, int(math.sqrt(n)) + 1):
if n % i == 0:
return False
return True
# Exemple d'utilisation
nombre = 17
if est_premier(nombre):
print(nombre, "est un nombre premier")
else:
print(nombre, "n'est pas un nombre premier")
Les tests de primalité plus sophistiqués (pour les nerds de maths)
Si vous êtes vraiment passionnés par les nombres premiers (et que vous avez un peu de background en maths), il existe des tests de primalité beaucoup plus complexes et performants, comme:
- Le test de Miller-Rabin (probabiliste, mais très rapide)
- Le test AKS (déterministe, et théoriquement polynomial, mais plus lent en pratique pour les nombres "petits")
Je ne vais pas rentrer dans les détails ici, car ça deviendrait vite très technique. Mais si ça vous intéresse, n'hésitez pas à faire des recherches sur Google (ou à me poser des questions en commentaires, je ferai de mon mieux pour vous répondre!)
Les nombres premiers, à quoi ça sert?
Bonne question! On pourrait se dire que les nombres premiers, c'est juste un truc de matheux qui s'ennuient. Mais en réalité, ils sont essentiels dans de nombreux domaines, notamment:
- La cryptographie: La sécurité de nombreux systèmes de chiffrement (comme RSA) repose sur la difficulté de factoriser de grands nombres en leurs facteurs premiers. Plus les nombres premiers utilisés sont grands, plus le chiffrement est difficile à casser. (D'où l'importance de trouver des nombres premiers toujours plus grands!)
- L'informatique: Les nombres premiers sont utilisés dans les tables de hachage, les générateurs de nombres aléatoires, et bien d'autres algorithmes.
- La physique: On les retrouve aussi, parfois, dans des modèles physiques (même si le lien est moins direct).
Bref, les nombres premiers sont loin d'être juste un concept abstrait. Ils sont au cœur de nombreuses technologies que nous utilisons tous les jours.
Conclusion
Voilà, j'espère que cet article vous a éclairé sur la façon de déterminer si un nombre est premier. Ce n'est pas toujours facile, mais avec les bonnes méthodes (et un peu de patience), on peut y arriver!
Et n'oubliez pas, même si vous ne devenez pas un expert en nombres premiers, c'est toujours bien d'avoir une petite idée de ce qu'ils sont et à quoi ils servent. Qui sait, ça pourrait vous être utile un jour... ou au moins vous permettre d'impressionner votre grand-mère lors du prochain partage de macarons!
