Algorithmes et Structures de Données

Factorisation en nombres premiers

Tout entier positif n ≥ 2 peut être exprimé comme le produit de nombres premiers :
La recherche des facteurs premiers d’un nombre présente de nombreuses applications : on peut ainsi compter facilement le nombre de ses diviseurs, déterminer plus intuitivement le plus grand commun diviseur (GCD) ou le plus petit commun multiple (LCM) de deux nombres, etc.
Pour représenter un nombre n (par exemple 300) comme produit de ses facteurs premiers, on peut démarrer avec le plus petit nombre premier p (2). Tant que n est divisible par p, on continue à le diviser par p (300 / 2 = 150, 150 / 2 = 75).
Ensuite, on augmente p de 1 (p = 3) et on essaie de diviser n par ce nouveau p. Si c’est possible, on procède de la même façon (75 / 3 = 25).
Puis on augmente à nouveau p de 1 (p = 4) et on tente de diviser n par ce nouveau p. Il n’est pas possible de diviser n par un nombre qui n’est pas premier, car on a déjà extrait tous les plus petits facteurs premiers de n. Dans l’exemple, 300 est divisible par 4, mais 75 ne l’est plus parce qu’on avait déjà divisé 300 plusieurs fois par 2 (or 4 est un multiple de 2). Comme on avance depuis le plus petit diviseur possible vers le plus grand, on est sûr qu’il n’y aura plus que des nombres premiers qui pourront diviser le reste de n.
À l’étape suivante, on incrémente p de 1 (p = 5) et on essaie de diviser n par ce nouveau p (75 / 5 = 5, puis 5 / 5 = 1). Ce processus se poursuit jusqu’à ce que le diviseur soit plus grand que . Si l’on arrive à un point où le diviseur dépasse ⇒ le reste de n est alors lui-même un nombre premier, qu’on ajoute directement en tant que facteur.
Ainsi, dans notre exemple, on peut écrire 300 comme .
n = ...                              # Représenter n comme un produit de nombres premiers
p, divisors, powers = 1, [], []      # facteur premier, diviseurs et leurs exposants

while p * p <= n:                    # tant que p <= sqrt(n)
    p += 1                           # Ajouter 1 au facteur premier à chaque itération
    if n % p != 0:                   # Ne rien faire si n n'est pas divisible par p
        continue
    
    divisors.append(p)               # n % p == 0 => ajouter p en tant que facteur premier
    powers.append(0)                 # l'exposant est initialement à 0
    while n % p == 0:                # diviser autant de fois que possible
        n //= p
        powers[-1] += 1              # augmenter l'exposant de 1 à chaque itération

if n > 1:                            # si p > sqrt(n) => n est lui-même un facteur premier
    divisors.append(n)               # ajouter n comme diviseur
    powers.append(1)                 # avec un exposant de 1

print(list(zip(divisors, powers)))   # afficher les facteurs et leurs exposants ensemble
À chaque itération de l’algorithme, on divise donc le nombre par son facteur premier quand c’est possible, en incrémentant l’exposant associé au fur et à mesure.
Voyons ce que donne pas à pas l’exécution de cet algorithme pour différents nombres :
n = 24
  1. p = 2, n = 24 (on a incrémenté p de 1 à 2 au début de la boucle) n % 2 == 0 ⇒ divisors = [2], powers = [0] n //= 2 ⇒ n = 12, powers = [1] n //= 2 ⇒ n = 6, powers = [2] n //= 2 ⇒ n = 3, powers = [3]
  1. p = 3, n = 3 ⇒ on arrête la boucle while car p * p = 9 est supérieur à 2
  1. n > 1 ⇒ divisors = [2, 3], powers = [3, 1]
n = 75
  1. p = 2, n = 75
  1. p = 3, n = 75 n % 3 == 0 ⇒ divisors = [3], powers = [0] n //= 3 ⇒ n = 25, powers = [1]
  1. p = 4, n = 25
  1. p = 5, n = 25 n % 5 == 0 ⇒ divisors = [3, 5], powers = [1, 0] n //= 5 ⇒ n = 5, powers = [1, 1] n //= 5 ⇒ n = 1, powers = [1, 2]
  1. p * p > n ⇒ on arrête la boucle while ⇒ divisors = [3, 5], powers = [1, 2]
n = 84
  1. p = 2, n = 84 n % 2 == 0 ⇒ divisors = [2], powers = [0] n //= 2 ⇒ n = 42, powers = [1] n //= 2 ⇒ n = 21, powers = [2]
  1. p = 3, n = 21 n % 3 == 0 ⇒ divisors = [2, 3], powers = [2, 0] n //= 3 ⇒ n = 7, powers = [2, 1]
  1. p * p > n ⇒ on arrête la boucle
  1. n > 1 ⇒ divisors = [2, 3, 7], powers = [2, 1, 1]
n = 31
  1. p = 2, n = 31
  1. p = 3, n = 31
  1. p = 4, n = 31
  1. p = 5, n = 31
  1. p = 6, n = 31
  1. p * p > n ⇒ on arrête la boucle
  1. n > 1 ⇒ divisors = [31], powers = [1]

Défi

Étant donné un entier n, vous devez trouver son plus grand facteur premier.

Entrée

La première ligne de l’entrée contient un seul entier n (2 ≤ n ≤ ).

Sortie

Le programme doit afficher le plus grand facteur premier de n.

Exemples

Input
Output
8
2
24
3
75
5
31
31
Bonus: Pourquoi ne vérifions-nous pas seulement les nombres premiers ?
Notre implémentation de l’algorithme teste tous les entiers 2, 3, 4, … jusqu’à . On serait tenté de ne regarder que les nombres premiers. Cependant, le fait de devoir repérer tous les nombres premiers jusqu’à exige plus de calculs que d’itérer de 2 jusqu’à et vérifier la divisibilité par chaque nombre : cela s’expliquerait par une complexité d’environ pour déterminer les nombres premiers, ce qui est plus coûteux que l’itération simple.
Pouvez-vous imaginer une situation où calculer les nombres premiers à l’avance, puis parcourir uniquement cette liste pour trouver les facteurs premiers, pourrait s’avérer plus optimal ?
 
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue