Décomposition en facteurs premiers
En arithmétique, la décomposition en produit de facteurs premiers, également désignée la factorisation entière en nombres premiers ou plus couramment la décomposition en facteurs premiers, cherche à écrire un entier naturel non nul sous la forme d'un produit de nombre premiers.
Exemple : le nombre 45 peut s'exprimer sous la forme 32 x 5.
Para définition, un nombre premier ne peut pas être décomposé en produit de plusieurs nombres premiers.
Le théorème de décomposition en produit de facteurs premiers s'énonce ainsi : « Tout entier strictement positif peut être écrit comme un produit de nombres premiers d'une unique façon, à l'ordre près des facteurs. ».
Algorithme : La première idée consiste à balayer la liste des nombres premiers en testant si le nombre premier p divise n. Si oui, en recommence avec n/p sinon on recommence le test avec le nombre premier suivant. L'algorithme s'arrête lorsque le nombre premier à tester devient supérieur à la racine carrée La racine carrée d'un nombre X correspond au nombre Y tel que : Y.Y = X. Lire plus du nombre qu'il est censé diviser.
Application : Calcul des facteurs premiers de 2056 et de 9828
2056 | 2 | 2 divise 2088, le quotient est 1028 |
1028 | 2 | 2 divise 1044, le quotient est 514 |
514 | 2 | 2 divise 514, le quotient est 257 |
257 |
| ni 2, ni 3, ni 5 ni 7, ni 11, ni 13 et 172 est plus grand que 257, 257 est premier |
On obtient donc 2056 = 23 x 257
9828 | 2 | 2 divise 9828, le quotient est 4914 |
4914 | 2 | 2 divise 9828, le quotient est 2457 |
2457 | 3 | 3 divise 2457, le quotient est 819 |
819 | 3 | 3 divise 819, le quotient est 273 |
273 | 3 | 3 divise 91, le quotient est 91 |
91 | 7 | 7 divise 91, le quotient est 13 |
13 |
| 72 est plus grand que 13, 13 est premier |
On obtient donc 9828 = 22 x 33 x 7 x 13