Décomposition en facteurs premiers
Décomposer un entier en facteurs premiers, lister ses diviseurs et vérifier s'il est premier.
Fonctionne entièrement dans votre navigateur. Rien n'est envoyé, journalisé ni conservé.
Décomposition en facteurs premiers
2^3 × 3^2 × 5
- Est-il premier ?
- non
- Facteurs premiers distincts
- 3
- Nombre de diviseurs
- 24
- Diviseurs
- 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60, 72, 90, 120, 180, 360
Tout entier supérieur à 1 est un produit de nombres premiers, et il n'en existe qu'un seul — c'est le théorème fondamental de l'arithmétique. Cette page le trouve, ainsi que tout ce qui en découle : combien de diviseurs le nombre possède, et lesquels.
Comment ça marche
Division d'essai, avec un raccourci : une fois 2 et 3 retirés, tout nombre premier restant se trouve d'un côté ou de l'autre d'un multiple de six, donc les candidats avancent de six en six au lieu de deux en deux. Ce qui survit au crible est lui-même premier et entre comme dernier facteur.
Les diviseurs sont construits à partir de la décomposition plutôt qu'en testant tous les nombres jusqu'à n. Un nombre écrit 2³ × 3² × 5 possède (3+1) × (2+1) × (1+1) = 24 diviseurs, chacun étant un choix du nombre d'exemplaires de chaque premier — les lister ne coûte donc rien une fois la décomposition connue.
Le plafond est de mille milliards. La division d'essai touche au plus la racine carrée du nombre, soit un million d'étapes à ce niveau — rapide. Au-delà, un nombre qui serait le produit de deux grands premiers laisserait la page chargée une minute ; elle refuse donc.
Exemples
| Cas | Saisie | Résultat |
|---|---|---|
| Un nombre très divisible | 360 | 2³ × 3² × 5 — 24 diviseurs |
| Un nombre premier | 97 | 97 — premier, 2 diviseurs |
| Une puissance de deux | 1024 | 2¹⁰ — 11 diviseurs |
Questions fréquentes
Pourquoi commencer à 2 plutôt qu'à 1 ?
Parce que 1 n'a pas de décomposition, et que le dire premier briserait l'unicité sur laquelle repose toute la matière : si 1 était premier, 6 vaudrait 2 × 3, et 1 × 2 × 3, et 1 × 1 × 2 × 3, et il n'y aurait plus une seule réponse. Zéro est pire encore — tout nombre le divise.
Combien de diviseurs un nombre possède-t-il ?
Ajoutez un à chaque exposant de la décomposition et multipliez. 360 vaut 2³ × 3² × 5, donc 4 × 3 × 2 = 24. Un nombre premier en a 2 — lui-même et 1 — et un carré parfait en a toujours un nombre impair, parce qu'un diviseur y est son propre partenaire.
Pourquoi un plafond ?
La division d'essai est exacte et rapide jusqu'au moment où elle ne l'est plus. Le pire cas est un produit de deux premiers proches de la racine carrée, et la limite ici est celle où ce cas revient encore dans le temps d'un chargement. Un refus dit ce qui s'est passé ; une expiration ne dit rien.
Est-ce ainsi qu'on casse une clé de chiffrement ?
Non, et c'est justement la question. RSA repose sur la difficulté de décomposer un nombre de quelques centaines de chiffres ; une division d'essai sur l'un d'eux survivrait à l'univers. Les méthodes qui font mieux existent et restent très loin du compte, ce qui est la raison pour laquelle le procédé fonctionne.
Bon à savoir
- Les diviseurs sont listés en entier jusqu'à soixante-quatre ; au-delà seul le compte est affiché, car une page de neuf cents nombres n'est lue par personne.