Décomposition en facteurs premiers
Chaque nombre naturel n > 1 possède une représentation unique, à l'exception de l'ordre des facteurs, en tant que produit de nombres premiers. (Théorème fondamental de la théorie des nombres)
La représentation unique n = p1e1 · p2e2 . . . pnen comme produit de puissances de nombres premiers est appelée décomposition canonique en facteurs premiers de n.
Le programme décompose tout entier naturel n inférieur à 1014 en ses puissances premières.
Exemples:
99999999999901 = 19001 · 5262880901 99999999999001 = 107 · 401 · 1327 · 1756309 99999999990001 = Nombre premier 3938980639167 = 314 · 77 999330136292431 = 999712 · 99991 1596644705119 = 909091 · 1756309 100000000000027 = 73² · 271 · 751 · 92203 100000000000037 = 1858741 · 53799857 100000000000047 = 3 · 7 · 83 · 57372346529 100000000000057 = 23 · 4347826086959 100000000000067 = Nombre premier 100000000000077 = 3 · 17 · 3299 · 594357 100000000000087 = 11 · 12647 · 718819411 100000000000097 = Nombre premier
11 = Nombre premier 101 = Nombre premier 1001 = 7 · 11 · 13 10001 = 73 · 137 100001 = 11 · 9091 1000001 = 101 · 9901 10000001 = 11 · 909091 100000001 = 17 · 5882353 1000000001 = 7 · 11 · 13 · 19 · 52579 10000000001 = 101 · 3541 · 27961 100000000001 = 112 · 23 · 4093 · 8779 1000000000001 = 73 · 137 · 99990001 10000000000001 = 11 · 859 · 1058313049 100000000000001 = 29 · 101 · 281 · 121499449 1000000000000001 = 7 · 11 · 13 · 211 · 241 · 2161 · 9091 10000000000000001 = 353 · 449 · 641 · 1409 · 69857
Les 7 premiers nombres parfaits
6 = 2 · 3 28 = 22 · 7 496 = 24 · 31 8128 = 26 · 127 33550336 = 212 · 8191 8589869056 = 216 · 131071 137438691328 = 218 · 524287
Complément
Au lieu d'un seul nombre, un intervalle de nombres ou une séquence de nombres peut également être décomposé en facteurs premiers. L'entrée est identique à l'élément de programme Suites et Séries.
Carl Friedrich Gauss (1777-1855) dans les Disquisitiones Arithmeticae (1801):
Il est si bien connu que le problème de la distinction entre les nombres premiers et les nombres composés et de les décomposer en leurs facteurs premiers est l'un des plus importants et des plus utiles dans toute l'arithmétique et a préoccupé la diligence et la sagesse des géomètres anciens et modernes, qu'il n'y a pas besoin de dire beaucoup de choses à ce sujet.
Voir aussi:
Nombres premiers