Nombres premiers

Avant de commencer

7 est premier (divisible par 1 et 7 seulement). 9 = 3 × 3 ne l'est pas. Comment détecter efficacement qu'un nombre est premier ?

1. Définition et premier algorithme

Version naïve : tester tous les diviseurs de 2 à n−1.

FUNCTION EstPremier_Naive(n : integer) : boolean;
VAR i : integer;
BEGIN
  IF n < 2 THEN
    EstPremier_Naive := false
  ELSE
  BEGIN
    EstPremier_Naive := true;
    FOR i := 2 TO n - 1 DO
      IF n MOD i = 0 THEN
        EstPremier_Naive := false;
  END;
END;

Inconvénient : O(n) opérations.

2. Optimisation : s'arrêter à √n

Si n = a × b avec a ≤ b, alors a ≤ √n. Donc s'il existe un diviseur, il existe forcément un diviseur ≤ √n. On peut s'arrêter là.

DEF FN EstPremier(n : entier) : booléen
  Si n < 2 Alors EstPremier ← Faux
  Sinon
    ok ← Vrai
    i ← 2
    Tant que (i * i ≤ n) ET ok Faire
      Si n mod i = 0 Alors ok ← Faux FinSi
      i ← i + 1
    FinTantQue
    EstPremier ← ok
  FinSi
Fin EstPremier

DEF FN EstPremier(n : entier) : booléen
  Si n < 2 Alors EstPremier ← Faux
  Sinon
    ok ← Vrai
    i ← 2
    Tant que (i * i ≤ n) ET ok Faire
      Si n mod i = 0 Alors ok ← Faux FinSi
      i ← i + 1
    FinTantQue
    EstPremier ← ok
  FinSi
Fin EstPremier

FUNCTION EstPremier(n : integer) : boolean;
VAR
  i : integer;
  ok : boolean;
BEGIN
  IF n < 2 THEN
    ok := false
  ELSE
  BEGIN
    ok := true;
    i := 2;
    WHILE (i * i <= n) AND ok DO
    BEGIN
      IF n MOD i = 0 THEN
        ok := false;
      i := i + 1;
    END;
  END;
  EstPremier := ok;
END;

Complexité : O(√n). Pour n = 10⁶, on teste au max 1000 valeurs au lieu de 1 000 000.

3. Liste des premiers jusqu'à N

PROCEDURE PremiersJusqu(N : integer);
VAR k : integer;
BEGIN
  FOR k := 2 TO N DO
    IF EstPremier(k) THEN
      Write(k, ' ');
  Writeln;
END;

PremiersJusqu(20) affiche : 2 3 5 7 11 13 17 19.

4. Exercices

PROGRAM Compte;
VAR n, k, cpt : integer;
BEGIN
  Write('N : ');
  Readln(n);
  cpt := 0;
  FOR k := 2 TO n DO
    IF EstPremier(k) THEN
      cpt := cpt + 1;
  Writeln('Nombre de premiers ≤ ', n, ' : ', cpt);
END.

PROGRAM Crible;
CONST N = 100;
VAR
  est_premier : ARRAY[2..N] OF boolean;
  i, j : integer;
BEGIN
  { Initialement, tous candidats }
  FOR i := 2 TO N DO
    est_premier[i] := true;

  { Marquage des multiples }
  FOR i := 2 TO N DO
    IF est_premier[i] THEN
    BEGIN
      j := i * 2;
      WHILE j <= N DO
      BEGIN
        est_premier[j] := false;
        j := j + i;
      END;
    END;

  { Affichage }
  FOR i := 2 TO N DO
    IF est_premier[i] THEN
      Write(i, ' ');
END.

5. Erreurs fréquentes au bac

• Oublier de traiter n < 2 (1, 0, négatifs ne sont pas premiers).
• Boucle FOR i := 2 TO n au lieu de s'arrêter à √n (très lent).
• Continuer à incrémenter i après avoir trouvé un diviseur (utiliser un drapeau ou un Sortir).

6. Quiz