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

Algorithmique > Nombres premiers [ Proposer une amélioration ]

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. 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).

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;