Vérificateur de nombres premiers
Vérifiez si un nombre de 40 chiffres maximum est premier. Avec décomposition en facteurs premiers, diviseurs, nombres premiers voisins et liste des premiers d'un intervalle.
Comment fonctionne le test de primalité
Un nombre premier est un nombre entier supérieur à 1 qui a exactement deux diviseurs : 1 et lui-même. 2, 3, 5, 7 et 11 sont premiers. Un nombre qui a plus de diviseurs, comme 12 (1, 2, 3, 4, 6, 12), est composé. 0 et 1 ne sont ni premiers ni composés. Tout nombre entier supérieur à 1 s'écrit d'une seule façon comme produit de nombres premiers, par exemple 360 = 2³ × 3² × 5.
Pour tester n, on le divise par chaque nombre premier jusqu'à √n. Si n = a × b, l'un des deux est forcément inférieur ou égal à √n. Si aucun nombre premier jusqu'à √n ne divise n, alors n est premier. Pour 221, √221 ≈ 14,9 et 221 ÷ 13 = 17, donc 221 n'est pas premier. Cette calculatrice utilise cette méthode jusqu'à mille milliards.
Pour les grands nombres, la division par essais est trop lente : la calculatrice utilise le test de Miller-Rabin. Il vérifie une propriété que possède tout nombre premier, avec plusieurs valeurs de test appelées bases. Avec les 13 premiers nombres premiers comme bases, le test est prouvé exact pour tout nombre inférieur à environ 3,3 × 10²⁴. Au-delà, 20 bases sont utilisées et le résultat est appelé premier probable. Les nombres composés sont décomposés avec la méthode rho de Pollard.
Avertissement: Cette calculatrice effectue des opérations mathématiques standard à usage général et éducatif uniquement. Elle ne remplace pas une vérification professionnelle — pour les calculs où la précision est essentielle, comme les déclarations financières, les travaux d'ingénierie ou les remises académiques, veuillez vérifier le résultat de manière indépendante.
Questions fréquemment posées
À propos de cette calculatrice
Ce vérificateur de nombres premiers vous dit tout de suite si un nombre entier est premier. Sinon, vous voyez sa décomposition en facteurs premiers et ses diviseurs. Il affiche aussi le nombre premier précédent et le suivant, repère les nombres premiers jumeaux et de Mersenne, et explique chaque étape pour les nombres jusqu'à mille milliards. L'onglet Nombres premiers d'un intervalle liste tous les premiers entre deux nombres.
Ce qui rend un nombre premier
Un nombre premier est un nombre entier supérieur à 1 qui a exactement deux diviseurs : 1 et lui-même. 2, 3, 5, 7, 11 et 13 sont les premiers nombres premiers. 2 est le seul nombre premier pair, car tout autre nombre pair est divisible par 2. Un nombre entier supérieur à 1 qui n'est pas premier est dit composé. 0 et 1 ne sont ni premiers ni composés.
Les nombres premiers sont les briques de tous les nombres entiers. Le théorème fondamental de l'arithmétique dit que tout nombre entier supérieur à 1 s'écrit d'une seule façon comme produit de nombres premiers, sans tenir compte de l'ordre. Par exemple, 360 = 2³ × 3² × 5. C'est cette décomposition que l'outil affiche pour les nombres composés.
Comment fonctionne le vérificateur
Petits et moyens nombres (jusqu'à mille milliards) : la division par essais. Pour tester n, l'outil le divise par chaque nombre premier jusqu'à √n. Cela suffit, car si n = a × b, alors a ou b est forcément inférieur ou égal à √n. Si aucun de ces nombres premiers ne divise n, n est premier. Pour 1 000 000 007, √n ≈ 31 623 : l'outil essaie les 3 401 nombres premiers jusqu'à 31 622 et constate qu'aucun ne le divise.
Grands nombres : le test de Miller-Rabin. Au-delà de mille milliards, l'outil utilise le test de Miller-Rabin. Tout nombre premier impair p réussit un contrôle qui consiste à écrire p − 1 = 2ˢ × d et à élever une valeur de test (une base) à la puissance d modulo p. Un nombre composé échoue pour la plupart des bases. Avec les 13 premiers nombres premiers (de 2 à 41) comme bases, le test est prouvé exact pour tout nombre inférieur à environ 3,3 × 10²⁴. Pour les nombres plus grands, l'outil utilise 20 bases et indique un nombre premier probable.
Décomposition : la méthode rho de Pollard. Pour décomposer un grand nombre composé, l'outil retire d'abord les petits facteurs premiers, puis utilise la méthode rho de Pollard, bien plus rapide que la division par essais. Les nombres dont tous les facteurs premiers sont très grands peuvent demander des années de calcul sur n'importe quel ordinateur. Dans ce cas, l'outil affiche la partie qu'il n'a pas pu décomposer.
Nombres premiers d'un intervalle : le crible. L'onglet intervalle utilise un crible d'Ératosthène segmenté. Il barre les multiples de chaque nombre premier jusqu'à √(À), et chaque nombre restant est premier. Il traite jusqu'à un million de nombres à la fois, n'importe où jusqu'à mille milliards.
Exemples
- 221 : √221 ≈ 14,9, donc l'outil teste 2, 3, 5, 7, 11 et 13. 221 ÷ 13 = 17, donc 221 = 13 × 17 est composé. Beaucoup pensent que 221 est premier parce qu'il est impair et ne finit pas par 5.
- 561 : 561 = 3 × 11 × 17. C'est le plus petit nombre de Carmichael, un nombre composé qui trompe le test simple de Fermat pour toute base sans facteur commun avec lui. Le test de Miller-Rabin n'a pas cette faiblesse.
- 2 147 483 647 : c'est 2³¹ − 1, un nombre premier de Mersenne et la plus grande valeur d'un entier signé de 32 bits en programmation. L'outil confirme qu'il est premier et l'indique comme nombre premier de Mersenne.
- 600 851 475 143 : = 71 × 839 × 1 471 × 6 857. Son plus grand facteur premier, 6 857, est la réponse d'un problème de programmation connu (Project Euler, problème 3).
Les nombres premiers deviennent plus rares quand les nombres grandissent, mais il n'y en a jamais de fin. Le théorème des nombres premiers dit que près d'un nombre n, environ 1 nombre sur ln(n) est premier. Près de mille milliards, ln(10¹²) ≈ 27,6 : un bloc de 200 000 nombres devrait contenir environ 7 238 nombres premiers. Entre 999 999 800 000 et 1 000 000 000 000, il y en a 7 213, ce que vous pouvez vérifier avec l'onglet intervalle.
Où sont utilisés les nombres premiers
- Sécurité sur Internet : le chiffrement RSA multiplie deux nombres premiers secrets de plusieurs centaines de chiffres. Tout le monde peut voir le produit, mais aucune méthode connue ne peut le décomposer en un temps raisonnable, et c'est ce qui protège la clé.
- Programmation : les tables de hachage utilisent souvent un nombre premier d'emplacements pour bien répartir les données, et les concours de programmation demandent souvent des réponses modulo le nombre premier 1 000 000 007.
- Records mathématiques : le projet GIMPS cherche de très grands nombres premiers de Mersenne. En octobre 2024, il a trouvé 2^136 279 841 − 1, un nombre premier de plus de 41 millions de chiffres.
- Enseignement : trouver des nombres premiers, faire des arbres de facteurs et compter des diviseurs sont des notions de base à l'école, et les étapes détaillées montrent chaque division.
- Vérification instantanée — Teste tout nombre entier jusqu'à 40 chiffres et indique s'il est premier, composé ou ni l'un ni l'autre (0 et 1).
- Décomposition et diviseurs — Décompose les nombres composés en facteurs premiers avec exposants et affiche le nombre de diviseurs et les diviseurs eux-mêmes.
- Étapes détaillées — Pour les nombres jusqu'à mille milliards, affiche √n, les nombres premiers testés et la division qui prouve la réponse.
- Nombres premiers d'un intervalle — Liste tous les nombres premiers entre deux nombres, jusqu'à mille milliards et un million de nombres à la fois, avec le nombre de paires de jumeaux.
- Nombres premiers voisins et particuliers — Affiche le nombre premier précédent et le suivant, et repère les nombres premiers jumeaux et de Mersenne.