Calculateur de Nombres Premiers et Factorisation
Ce calculateur fait deux choses à la fois : il vous dit si un nombre entier est premier et il le décompose en ses facteurs premiers, en se mettant à jour au fur et à mesure de la frappe. Un nombre premier est un nombre entier supérieur à 1 dont les seuls diviseurs sont 1 et lui-même — comme 2, 3, 5, 7 et 11. Tout nombre qui n'est pas premier (un nombre composé) peut s'écrire comme un produit unique de facteurs premiers, ce qui est à la base d'une grande partie de la théorie des nombres et des algorithmes utilisés en cryptographie.
Est-il premier ?
Facteurs premiers
Un nombre premier n'est divisible que par 1 et par lui-même. La décomposition montre les facteurs premiers multipliés entre eux.
Publicidad
Comment ça fonctionne
Pour vérifier si un nombre n est premier, le calculateur traite les petits cas (les nombres inférieurs à 2 ne sont jamais premiers, 2 et 3 le sont) puis essaie de diviser n par chaque nombre impair de 3 jusqu'à la racine carrée de n. Si l'un d'eux divise n exactement, n est composé ; si aucun ne le fait, n est premier. Il suffit de tester jusqu'à la racine carrée car si n avait un diviseur plus grand que sa racine, il en aurait aussi un plus petit associé. Pour la factorisation, le calculateur retire de façon répétée le plus petit facteur possible : il divise par 2 tant qu'il le peut, puis par 3, puis par 5, et ainsi de suite, en collectant chaque facteur jusqu'à ce qu'il ne reste plus rien. Pour 60 cela donne 2 × 2 × 3 × 5, et pour un premier comme 97 le seul facteur est 97 lui-même.
Les nombres premiers jusqu'à 100
Entre 1 et 100 il y a exactement 25 nombres premiers. Le 2 est le seul nombre premier pair : tout autre nombre pair est divisible par 2, donc à partir de là tous les premiers sont impairs (même si tout impair n'est pas premier, comme 9 = 3 × 3 ou 15 = 3 × 5). Une façon classique de les trouver est le crible d'Ératosthène : on écrit les nombres à partir de 2 et on raye les multiples de chaque premier (ceux de 2, puis de 3, de 5…) ; ce qui reste non rayé est premier. Voici la liste complète jusqu'à 100.
| Plage | Nombres premiers |
|---|---|
| 1 – 50 | 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 |
| 51 – 100 | 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 |
Comment vérifier à la main si un nombre est premier
Pour savoir si un nombre n est premier, il suffit de tester si un nombre de 2 jusqu'à la racine carrée de n le divise. Si aucun ne le divise exactement, n est premier. Par exemple, la racine carrée de 97 vaut environ 9,85, il suffit donc de tester 2, 3, 5 et 7 : comme aucun ne le divise, 97 est premier. En revanche 91 semble premier à première vue, mais 91 = 7 × 13, il est donc composé. Ne tester que jusqu'à la racine carrée fonctionne car si n avait un diviseur plus grand que sa racine, le quotient serait un diviseur plus petit que l'on aurait déjà trouvé.
Publicidad
Preguntas frecuentes
- Qu'est-ce qu'un nombre premier ?
- Un nombre premier est un nombre entier supérieur à 1 qui a exactement deux diviseurs : 1 et lui-même. Les premiers nombres premiers sont 2, 3, 5, 7, 11, 13 et 17. Le 2 est le seul nombre premier pair, car tout autre nombre pair est divisible par 2.
- 1 est-il un nombre premier ?
- Non. Par définition un nombre premier doit avoir exactement deux diviseurs distincts, et 1 n'a qu'un seul diviseur (lui-même). Pour la même raison, 0 et les nombres négatifs ne sont pas premiers. Le plus petit nombre premier est 2.
- Qu'est-ce que la factorisation en nombres premiers ?
- La factorisation en nombres premiers consiste à écrire un nombre comme produit de nombres premiers. Par exemple, 60 = 2 × 2 × 3 × 5. Le théorème fondamental de l'arithmétique garantit que tout nombre entier supérieur à 1 possède exactement une telle factorisation, à l'ordre des facteurs près.
- Comment le calculateur vérifie-t-il si un nombre est premier ?
- Il écarte les nombres inférieurs à 2 et les nombres pairs supérieurs à 2, puis essaie de diviser par chaque nombre impair jusqu'à la racine carrée de l'entrée. Si aucun ne divise exactement, le nombre est premier. S'arrêter à la racine carrée rend le test rapide même pour de grands nombres.
- Pourquoi la factorisation en nombres premiers est-elle importante ?
- La factorisation en nombres premiers est à la base de la réduction des fractions, de la recherche du plus grand commun diviseur et du plus petit commun multiple, et de la cryptographie à clé publique comme RSA, dont la sécurité repose sur la difficulté de factoriser de très grands nombres en leurs facteurs premiers.