Les n premiers nombres premiers et le crible d'Eratosthène

Algorithmique > Nombres premiers [ Donner son avis ]

Description du problème

On cherche la liste des tous les nombres premiers de N inférieurs ou égaux à n.
On rappelle qu'un nombre premier p est défini comme un entier n'admettant que deux diviseurs (1 et p).
Pour n=10, on obtient donc la suite : 2, 3, 5, 7.

Pour résoudre ce problème, on utilise le crible d'Eratosthène.

Complexité en temps et en mémoire

La place mémoire est un facteur important dans cet algorithme, puisque le crible d'Eratosthène nécessite l'utilisation d'un tableau, a priori de taille n.

• La version simple utilise un espace mémoire de n octets.
• La version rapide utilise un espace mémoire de n/2 octets.

Les deux algorithmes s'éxécutent en temps linéaire Ω(n). En effet, on ne s'occupe de chaque nombre qu'une seule fois (ou bien deux pour certains).

• Pour n de l'ordre de 10³, les deux algorithmes sont équivalents.
• Pour n de l'ordre de 10⁴, l'algorithme « rapide » économise environ 10% de temps.
• Pour n de l'ordre de 10⁶, l'algorithme « rapide » économise plus de 70% de temps de calcul. Ceci s'explique par sa faible utilisation en mémoire qui lui permet de travailler en mémoire vive, là ou l'algorithme simple ne peut plus le faire.

Code (Pascal) - Version simple

type TIntegerArray = Array of Integer;

function NombresPremiers(N: Integer): TIntegerArray;

  procedure AddResult(I: Integer);
  begin
    SetLength(Result,Length(Result)+1);
    Result[Length(Result)-1]:=I;
  end;

var
  Prime: Array of Boolean;
  I,J,StopN: Integer;
begin

  SetLength(Result,0);
  
  SetLength(Prime,N+1);
  FillChar(Prime[0],N+1,255);

  StopN:=Trunc(SQRT(N))+1;
  
  For I:= 2 to StopN do
    if (Prime[I]) then
      begin
        AddResult(I);
        For J:= 1 to (N div I) do Prime[I*J]:=False;
      end;
  For I:= StopN+1 to N do
    if (Prime[I]) then AddResult(I);

  Finalize(Prime)

end;

Code (Pascal) - Version rapide

Dans le code qui suit, le tableau principal qui sert au crible d'Eratosthène ne va pas contenir les nombres pairs.

Type TIntegerArray = Array of Integer;

function NombresPremiers(N: Integer): TIntegerArray;

  procedure AddResult(I: Integer);
  begin
    SetLength(Result,Length(Result)+1);
    Result[Length(Result)-1]:=I;
  end;

var Prime: Array of Boolean;
    C,A,I,J,StopN: Integer;
begin

  SetLength(Result,0);

  StopN:=Ceil((SQRT(N)-3)/2);
  C:=Ceil(N/2)-1;
  SetLength(Prime,C);
  FillChar(Prime[0],C,255);

  AddResult(2);
  For I:= 0 to StopN do
    if (Prime[I]) then
      begin
        A:=I*2+3;
        AddResult(A);
        For J:= 0 to Ceil((N div A)/2)-1 do
          Prime[2*I*J+3*J+I]:=False;
      end;
  For I:= StopN+1 to C-1 do
    if (Prime[I]) then
      AddResult(I*2+3);

  Finalize(Prime);

end;