Masar
Masar
Bac Tunisie
Informatique/RA-D
Entraîner la reconnaissance
RA-DAlgorithmes récurrents et arithmétiques

Algorithmes arithmétiques — Euclide, primalité, décomposition en facteurs premiers

Idée directrice

L'énoncé donne un ou deux entiers et demande d'implémenter des algorithmes classiques : calcul du PGCD par l'algorithme d'Euclide, test de primalité par essais de division jusqu'à n\sqrt{n}, ou décomposition en facteurs premiers. La traduction du raisonnement mathématique en boucles est le point central.

Signature de reconnaissance — l'énoncé se trahit ainsi

« Écrire l'algorithme du PGCD par la méthode d'Euclide » ; « Donner la trace de l'algorithme d'Euclide pour … » ; « Écrire une fonction qui teste si un entier est premier » ; « Écrire un algorithme de décomposition en facteurs premiers »

Sujet principal

Exercice — dans l'esprit des sujets du bac

3 questionsCorrigé masqué
  1. Écrire l'algorithme itératif de l'algorithme d'Euclide pour calculer PGCD(a, b). Appliquer à PGCD(252, 84) en donnant la trace (tableau des valeurs de a et b).
  2. Écrire une fonction EstPremier(n) qui retourne VRAI si nn est premier.
    1. Pourquoi suffit-il de tester les diviseurs jusqu'à ⌊n⌋\lfloor \sqrt{n} \rfloor ?
    2. Tester si 97 est premier. Combien de divisions sont nécessaires ?
  3. Écrire une procédure Decomposer(n) qui affiche la décomposition de nn en facteurs premiers. Appliquer à n=360n = 360.
Voir la correction commentéeAprès avoir posé votre démarche

1. PGCD itératif (Euclide). Tant que b≠0, remplacer (a,b) par (b, a mod b).

TDOL : r entier (reste). Type/Nature : a, b entiers.

DEF FN PGCD(a, b : entier) : entier
Variables r : entier
Début
  TantQue b ≠ 0 faire
    r ← a mod b ; a ← b ; b ← r
  FinTantQue
  Retourner a
Fin

Trace pour PGCD(252, 84) : (252, 84) → (84, 0). On retourne 84.

2. Test de primalité. Un entier n ≥ 2 est premier s'il n'a aucun diviseur dans 2..⌊√n⌋.

DEF FN EstPremier(n : entier) : booléen
Variables i : entier
Début
  Si n < 2 alors Retourner Faux FinSi
  Pour i de 2 à Tronc(Racine(n)) faire
    Si n mod i = 0 alors Retourner Faux FinSi
  FinPour
  Retourner Vrai
Fin

2.(a) Pourquoi s'arrêter à ⌊√n⌋. Si n = d × q avec d ≤ q, alors d² ≤ d × q = n, donc d ≤ √n : tout entier composé possède un diviseur au plus égal à sa racine carrée. Ne trouver aucun diviseur jusqu'à ⌊√n⌋ suffit donc à conclure.
2.(b) Test de 97. ⌊√97⌋ = 9 : on effectue les divisions par 2, 3, 4, 5, 6, 7, 8, 9, soit 8 divisions, aucune n'a un reste nul → 97 est premier. (Sans la borne, il en faudrait 95.)
3. Décomposition en facteurs premiers — appliquer à n = 360.

DEF PROC Decomposer(n : entier)
Variables d : entier
Début
  d ← 2
  TantQue d * d ≤ n faire
    TantQue n mod d = 0 faire
      Écrire(d) ; n ← n div d
    FinTantQue
    d ← d + 1
  FinTantQue
  Si n > 1 alors Écrire(n) FinSi
Fin

360 = 2 × 2 × 2 × 3 × 3 × 5 = 23×32×52^3 \times 3^2 \times 5. Contrainte : n dans [2..+∞[ ; ne pas oublier d'afficher n s'il reste > 1 en fin de boucle.

Équivalent Python (extrait).

def pgcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a
print(pgcd(252, 84))

Méthode / Automatismes
  • PGCD itératif (Euclide) : TantQue b≠0 : r←a mod b ; a←b ; b←r. Résultat : a.
  • Primalité : tester les diviseurs de 2 à ⌊n⌋\lfloor\sqrt{n}\rfloor. Cas particuliers : n<2 → non premier.
  • Décomposition : boucle sur d à partir de 2, diviser n tant que divisible, puis incrémenter d.
  • Si n>1 en fin de boucle : n est lui-même un facteur premier.
  • PPCM(a,b)=a×bPGCD(a,b)\text{PPCM}(a,b) = \dfrac{a \times b}{\text{PGCD}(a,b)} — souvent demandé en même temps que PGCD.
Pièges classiques

Pièges fréquents : oublier le cas n<2 dans le test de primalité ; s'arrêter à n−1\sqrt{n}-1 au lieu de ⌊n⌋\lfloor\sqrt{n}\rfloor ; dans la décomposition, oublier d'afficher n si n>1 en fin de boucle (n est alors un facteur premier).

Variantes rencontrées : PGCD de trois entiers ; vérification si deux entiers sont premiers entre eux (pgcd⁡=1\pgcd = 1) ; liste de tous les nombres premiers jusqu'à N (crible d'Ératosthène).