Décomposition en facteurs premiers et factorielle

Avant de commencer

60 = 2 × 2 × 3 × 5. C'est la décomposition en facteurs premiers. Pour n! (factorielle), c'est un grand nombre vite : 10! = 3 628 800. Comment calculer et représenter ces nombres ?

1. Décomposition en facteurs premiers

Principe : on divise n par les premiers successifs (2, 3, 5, …) tant que possible. À chaque division réussie, on note le facteur.

PROCEDURE Decomposer(n : integer);
VAR p : integer;
BEGIN
  p := 2;
  Write(n, ' = ');
  WHILE n > 1 DO
  BEGIN
    WHILE n MOD p = 0 DO
    BEGIN
      Write(p);
      n := n DIV p;
      IF n > 1 THEN Write(' x ');
    END;
    p := p + 1;
  END;
  Writeln;
END;

Trace pour 60 : 60/2=30, 30/2=15, 15/3=5, 5/5=1. Affichage : 60 = 2 x 2 x 3 x 5.

2. Factorielle

n! = 1 × 2 × 3 × … × n. Cas particulier : 0! = 1.

{ Attention : retour 'longint' obligatoire car n! déborde 'integer' (16 bits)
  dès n = 8 en Turbo Pascal. Voir section 3 sur les limites de capacité. }
FUNCTION Factorielle(n : integer) : longint;
VAR
  i : integer;
  f : longint;
BEGIN
  f := 1;
  FOR i := 2 TO n DO
    f := f * i;
  Factorielle := f;
END;

Trace pour 5! : 1, 2, 6, 24, 120.

3. Limites de capacité

En Pascal standard, integer est typiquement signé sur 16 ou 32 bits.

Au-delà, dépassement de capacité silencieux (le résultat tourne).

FUNCTION Factorielle(n : integer) : longint;   { ou int64 }
VAR
  i : integer;
  f : longint;
BEGIN
  f := 1;
  FOR i := 2 TO n DO
    f := f * i;
  Factorielle := f;
END;

4. Exercices

FUNCTION NbDiviseurs(n : integer) : integer;
VAR p, exp, res : integer;
BEGIN
  res := 1;
  p := 2;
  WHILE n > 1 DO
  BEGIN
    exp := 0;
    WHILE n MOD p = 0 DO
    BEGIN
      exp := exp + 1;
      n := n DIV p;
    END;
    IF exp > 0 THEN
      res := res * (exp + 1);
    p := p + 1;
  END;
  NbDiviseurs := res;
END;

{ Exemple : 12 = 2²×3¹ → (2+1)(1+1) = 6 diviseurs (1,2,3,4,6,12) }

FUNCTION Binomial(n, k : integer) : longint;
VAR i : integer;
  res : longint;
BEGIN
  IF k > n - k THEN k := n - k;   { symétrie }
  res := 1;
  FOR i := 1 TO k DO
  BEGIN
    res := res * (n - i + 1);
    res := res DIV i;
  END;
  Binomial := res;
END;

5. Erreurs fréquentes au bac

• Initialiser f := 0 au lieu de 1 pour la factorielle (multiplie par 0).
• Démarrer la boucle à 1 au lieu de 2 (multiplier par 1 est inutile mais pas faux).
• Utiliser integer pour n! quand n ≥ 8 → overflow.

6. Quiz