Livre_silo 30 août 2013 16:32 Page 355
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
355
A – Travaux pratiques
A.6.2 Décomposition en facteurs premiers
Étant donné n ∈ N, n s’ écrit de manière unique sous la forme :
n = p 1 p 2 . . . p k
avec p 1 ⩽ p 2 ⩽ . . . ⩽ p k et p i premier
On se propose ici de déterminer les facteurs p i .
Méthode par division
La méthode la plus simple est la suivante : si n > 1, on teste sa divisibilité par les nombres
premiers successifs p = 2, 3, 5, . . . jusqu’à ce que n ≡ 0 (mod p). On remplace alors n
par n/p et on reprend à p. Lorsque n ̸ ≡ 0 (mod p) avec ⌊n/p⌋ ⩽ p, on s’arrête, avec
n premier.
Cette méthode a l’inconvénient qu’il faut déterminer la suite des nombres premiers. Toutefois, on peut simplifier cette méthode de la façon suivante. Soit n ∈ N
⋆ dont on souhaite
déterminer la décomposition en facteurs premiers. Soit (d i ) une suite d’entiers
2 = d 0 < d 1 < d 2 < . . .
qui inclut tous les nombres premiers ⩽
√
n et au moins un élément d k ⩾
√
n. Alors,
l’algorithme suivant détermine la décomposition de n en facteurs premiers :
A1 t ← 0, k ← 0.
A2 Si n = 1 c’est terminé.
A3 On divise n par d k : n = qd k + r avec (0 ⩽ r < d k ).
A4 Si r = 0 alors t ← t + 1, p t ← d k , n ← q. Aller en A2.
A5 Si q > d k alors k ← k + 1 et aller en A3.
A6 t ← t + 1, p t ← n. C’est terminé.
Écrire une fonction decomp prenant en argument l’entier n, une suite (d k ) pour n, et renvoyant la suite croissante des facteurs premiers p i de n.
On pourrait prendre pour (d k ) la suite 2, 3, 5, 7, . . ., c’est-à-dire 2 puis tous les impairs
à partir de 3. On prendra plutôt la suite 2, 3, 5, 7, 11, 13, 17, 19, 23, 25, . . ., c’est-à-dire
ajouter alternativement 2 et 4 à partir de 5 (on supprime ainsi tous les multiples de 2 et 3).
Écrire une fonction dk prenant n en argument et renvoyant une telle suite d 0 , . . . , d k avec
d k ⩾
√
n.
On peut gagner encore 20 % sur cette suite en supprimant les entiers de la forme 30m ± 5,
et encore 14 % en supprimant les multiples de 7, etc. Si n est petit, on peut utiliser une
table des nombres premiers (pour n ⩽ 10
6 , il n’y a que 168 nombres premiers).
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
355
A – Travaux pratiques
A.6.2 Décomposition en facteurs premiers
Étant donné n ∈ N, n s’ écrit de manière unique sous la forme :
n = p 1 p 2 . . . p k
avec p 1 ⩽ p 2 ⩽ . . . ⩽ p k et p i premier
On se propose ici de déterminer les facteurs p i .
Méthode par division
La méthode la plus simple est la suivante : si n > 1, on teste sa divisibilité par les nombres
premiers successifs p = 2, 3, 5, . . . jusqu’à ce que n ≡ 0 (mod p). On remplace alors n
par n/p et on reprend à p. Lorsque n ̸ ≡ 0 (mod p) avec ⌊n/p⌋ ⩽ p, on s’arrête, avec
n premier.
Cette méthode a l’inconvénient qu’il faut déterminer la suite des nombres premiers. Toutefois, on peut simplifier cette méthode de la façon suivante. Soit n ∈ N
⋆ dont on souhaite
déterminer la décomposition en facteurs premiers. Soit (d i ) une suite d’entiers
2 = d 0 < d 1 < d 2 < . . .
qui inclut tous les nombres premiers ⩽
√
n et au moins un élément d k ⩾
√
n. Alors,
l’algorithme suivant détermine la décomposition de n en facteurs premiers :
A1 t ← 0, k ← 0.
A2 Si n = 1 c’est terminé.
A3 On divise n par d k : n = qd k + r avec (0 ⩽ r < d k ).
A4 Si r = 0 alors t ← t + 1, p t ← d k , n ← q. Aller en A2.
A5 Si q > d k alors k ← k + 1 et aller en A3.
A6 t ← t + 1, p t ← n. C’est terminé.
Écrire une fonction decomp prenant en argument l’entier n, une suite (d k ) pour n, et renvoyant la suite croissante des facteurs premiers p i de n.
On pourrait prendre pour (d k ) la suite 2, 3, 5, 7, . . ., c’est-à-dire 2 puis tous les impairs
à partir de 3. On prendra plutôt la suite 2, 3, 5, 7, 11, 13, 17, 19, 23, 25, . . ., c’est-à-dire
ajouter alternativement 2 et 4 à partir de 5 (on supprime ainsi tous les multiples de 2 et 3).
Écrire une fonction dk prenant n en argument et renvoyant une telle suite d 0 , . . . , d k avec
d k ⩾
√
n.
On peut gagner encore 20 % sur cette suite en supprimant les entiers de la forme 30m ± 5,
et encore 14 % en supprimant les multiples de 7, etc. Si n est petit, on peut utiliser une
table des nombres premiers (pour n ⩽ 10
6 , il n’y a que 168 nombres premiers).