Tous les défis
Moyen 0 résolus 0 % de réussite

Décomposition en facteurs premiers

Décomposez un nombre en facteurs premiers, du plus petit au plus grand, avec répétition.

Ce que vous allez apprendre

  • Diviser par chaque facteur autant de fois qu'il apparaît
  • Arrêter les divisions dès que d × d dépasse ce qui reste
  • Comprendre qu'un reste supérieur à 1 est un facteur premier

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

Exemple 1
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].

Exemple 2
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.

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

Aucune solution validée pour l'instant. Résolvez-le et prenez la première place.

Apprenez des autres

Solutions de la communauté

Aucune solution publiée pour l'instant. Résolvez ce défi pour partager la première.