Vérifiez si un nombre est premier, obtenez sa factorisation en nombres premiers et listez les nombres premiers jusqu'à n avec le crible d'Ératosthène.
Définition et propriétés des nombres premiers
Un nombre premier est un entier naturel supérieur à 1 qui n'admet que deux diviseurs : 1 et lui-même. Les 20 premiers nombres premiers sont : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71. Le nombre 2 est le seul nombre premier pair. Euclide a démontré vers 300 av. J.-C. qu'il existe une infinité de nombres premiers.
Théorème fondamental de l'arithmétique
Tout entier naturel > 1 s'écrit de façon unique comme produit de facteurs premiers (à l'ordre près). Cette factorisation est unique : 12 = 2² × 3 ; 360 = 2³ × 3² × 5 ; 97 est premier (factorisation triviale : 97). Ce théorème est fondamental en cryptographie (RSA repose sur la difficulté de factoriser de grands nombres).
Crible d'Ératosthène
L'algorithme le plus efficace pour lister tous les nombres premiers jusqu'à n est le crible d'Ératosthène (250 av. J.-C.) : on commence avec tous les nombres de 2 à n, puis on élimine successivement tous les multiples de chaque nombre premier trouvé. La complexité est O(n log log n), quasi-linéaire. Il reste efficace jusqu'à n = 10⁸ en mémoire raisonnable.
Applications en cryptographie
Le chiffrement RSA (Rivest-Shamir-Adleman, 1977) repose sur la difficulté de factoriser le produit de deux grands nombres premiers. En 2026, les clés RSA de 2 048 bits (produit de deux premiers d'environ 617 chiffres décimaux) sont considérées sûres pour 10 ans. Les ordinateurs quantiques (algorithme de Shor) menacent à terme la sécurité de RSA, ce qui accélère le développement de la cryptographie post-quantique (NIST, 2024).
Questions fréquentes
1 est-il un nombre premier ?
Non, par convention. La définition exige exactement deux diviseurs distincts. 1 n'a qu'un seul diviseur (lui-même). Cette exclusion est nécessaire pour que la factorisation en nombres premiers soit unique.
Comment tester rapidement si un grand nombre est premier ?
Le test de Miller-Rabin (probabiliste) est très efficace pour les grands nombres. En Python : sympy.isprime(n) ou gmpy2.is_prime(n). Pour n < 3 317 044 064 679 887 385 961 981, le test de Miller-Rabin avec certaines bases spécifiques est déterministe.
Quel est le plus grand nombre premier connu ?
En mars 2024, le plus grand nombre premier connu est M136279841 = 2^136279841 - 1, un nombre de Mersenne découvert par le GIMPS (Great Internet Mersenne Prime Search). Il a 41 024 320 chiffres décimaux.
Qu'est-ce que la conjecture de Goldbach ?
Goldbach (1742) a conjecturé que tout entier pair > 2 est la somme de deux nombres premiers. Exemple : 4=2+2, 6=3+3, 8=3+5, 100=3+97. Vérifiée jusqu'à 4×10¹⁸ (2013) mais non prouvée en général — c'est l'un des problèmes ouverts les plus célèbres des mathématiques.
Les nombres premiers sont-ils utiles dans la vie quotidienne ?
Oui : toutes les communications sécurisées (HTTPS, WhatsApp, carte bancaire) reposent sur la cryptographie asymétrique basée sur les nombres premiers. Chaque fois que vous voyez le cadenas dans votre navigateur, des nombres premiers de plusieurs centaines de chiffres travaillent pour vous.