Problème
Tout entier supérieur à 1 s'écrit comme un produit de nombres premiers d'une seule façon, à l'ordre des facteurs près (c'est le théorème fondamental de l'arithmétique). Par exemple, 360 = 2 × 2 × 2 × 3 × 3 × 5. Trouver cette liste s'appelle la décomposition en facteurs premiers.
Implémentez prime_factorization(n).
n peut atteindre 10^12. La méthode classique est donc celle des divisions successives : divisez par 2 tant que c'est possible, puis par 3, et ainsi de suite. Il suffit d'essayer les diviseurs d tant que d × d ≤ la partie de n qui reste à décomposer. Ce qui reste au-dessus de 1 à la fin est lui-même premier. Le travail reste ainsi limité à environ √n ≈ 10^6 étapes, même quand n est un grand nombre premier ou le produit de deux grands nombres premiers.
Entrée
n : le nombre à décomposer.
Sortie
Renvoyez les facteurs premiers de n par ordre croissant, en répétant chaque nombre premier autant de fois qu'il divise n, de sorte que le produit de la liste soit égal à n. Pour n = 1, renvoyez une liste vide. Si n est premier, la liste contient le seul élément n.
Contraintes
1 ≤ n ≤ 10^12
Exemples
Entrée :
n = 360
Sortie attendue :
expected = [2, 2, 2, 3, 3, 5]
Entrée :
long long n = 360;
Sortie attendue :
std::vector<long long> expected = {2, 2, 2, 3, 3, 5};
Entrée :
long n = 360;
Sortie attendue :
long[] expected = new long[] {2, 2, 2, 3, 3, 5};
Explication
360 = 2 × 180 = 2 × 2 × 90 = 2 × 2 × 2 × 45 = 2 × 2 × 2 × 3 × 15 = 2 × 2 × 2 × 3 × 3 × 5, donc la réponse est [2, 2, 2, 3, 3, 5].
Entrée :
n = 97
Sortie attendue :
expected = [97]
Entrée :
long long n = 97;
Sortie attendue :
std::vector<long long> expected = {97};
Entrée :
long n = 97;
Sortie attendue :
long[] expected = new long[] {97};
Explication
Aucun nombre premier inférieur à √97 ≈ 9,8 (2, 3, 5, 7) ne divise 97, donc 97 est premier et la réponse est [97].
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Divisez par 2 tant que c'est possible, puis passez à 3, 5, 7, et ainsi de suite.
Indice 2
Réduisez n chaque fois que vous trouvez un facteur, et comparez d × d avec ce n réduit.
Indice 3
S'il reste quelque chose de supérieur à 1 après la boucle, c'est le plus grand facteur premier.
Complexité attendue
temps O(√n), espace supplémentaire O(log n) pour le résultat
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.