O Crivo de Eratosthenes é um algoritmo que nos permite obter o conjunto dos números primos menores de que um determinado valor.

Suponhamos que se quer saber os números primos até 20.

• Inicialmente cria-se o conjunto {2,3,4,…,20}
• Selecciona-se o primeiro elemento e remove-se todos os seus múltiplos do conjunto (obtendo-se o conjunto {2,3,5,7,…,19});
• Passa-se para o elemento seguinte e repete-se o procedimento anterior, isto é, remove-se os múltiplos de 3 (fica-se com {2,3,5,7,11,13,17,19});
• Repete-se o mesmo passo para o 5 (e depois para o 7, para o 11, para o 13, …);
• No final obtém-se o conjunto {2,3,5,7,11,13,17,19}, ou seja, o conjunto dos números primos até 20.

int eratosthenes(char vals[DIM])
{
  int i,j;
 
  for(i=0;i<DIM;i++)
    vals[i]=1;
 
  vals[0]=0;
  vals[1]=0;
  for(i=2;i<DIM;i++)
    if(vals[i])
      for(j=i*i;j<DIM;j+=i)
        vals[j]=0;
 
  return 0;
}

void markNonPrimes(int startLine, int listSize, int currentPrime, int jump, char *main6, char *side6) {
    for (int i = startLine + currentPrime - jump; i < listSize; i += currentPrime) {
        if (i + jump < listSize) { main6[i + jump] = -1; }
 
        side6[i] = -1;
    }
}
 
void erathostenesEuler(char *left6, char *right6, int listSize) {
    int sqroot = sqrt(listSize);
 
    for (int i = 0; i < sqroot; i++) {
        int jump = (i + 1) * 2;
        int l = (left6[i] == 0) ? (i + 1) * 6 - 1 : -1;
        int r = (right6[i] == 0) ? (i + 1) * 6 + 1 : -1;
 
        if (l != -1) { markNonPrimes(i, listSize, l, jump, left6, right6); }
        if (r != -1) { markNonPrimes(i, listSize, r, jump, right6, left6); }
    }
}

Exemplo de utilização:

#define maximum 1000000000
 
int main(int argc, char *argv[]) {
    int listSize = maximum / 6;
 
    // inicialização a zero
    char* left6 = calloc(listSize, sizeof(char));
    char* right6 = calloc(listSize, sizeof(char));
 
    erathostenesEuler(left6, right6, listSize);
}

Nota: Assume-se que o 2 e o 3 são primos automaticamente. Os índices da left6 podem ser convertidos no número com a fórmula 6 * i - 1 e os da right6 com 6 * i + 1. Os índices do array com 0 são primos.

eratosthenes :: [Int] -> [Int]
eratosthenes []    = []
eratosthenes (h:t) = h : (eratosthenes (filter (x -> mod x h /= 0) t))
 
-- conjunto dos primos menores ou iguais a 'x'
 
primes :: Int -> [Int]
primes x = eratosthenes [2..x]

Apresentam-se duas formas de implementar o Crivo com variação dos tipos de dados utilizados.

program crivo_eratosthenes;
uses strutils;
 
type TList   = array of LongWord;
     TFnBool = function (n : LongWord) : Boolean;
 
(* Métodos complementares *)
procedure WriteList(l : TList);
var i : LongWord;
begin
   write('[');
   for i := Low(l) to High(l) do
      write(l[i], IfThen(i = High(l), '', ', '));
   write(']');
end;
 
 
function ReadInt : LongWord;
begin
   readln(ReadInt);
end;
 
 
function IsNotZero(n : LongWord) : Boolean;
begin
   IsNotZero := (n <> 0);
end;
 
 
function Filter(l : TList; f : TFnBool) : TList;
var elem : LongWord;
begin
   SetLength(Filter, 0);
   for elem in l do
      if f(elem) then begin
         SetLength(Filter, Succ(Length(Filter)));
         Filter[High(Filter)] := elem;
      end;
end;
 
 
(* Algoritmo - Crivo de Eratosthenes *)
function GetPrimes(lim : LongWord) : TList;
var i, j : LongWord;
begin
   SetLength(GetPrimes, lim-2);
   for i := 2 to lim do
      GetPrimes[i-2] := i;
 
   i := 2;
   while (i < lim) do begin
      j := Sqr(i);
      while (j <= lim) do begin
         GetPrimes[j-2] := 0;
         Inc(j, i);
      end;
      Inc(i);
   end;
end;
 
 
(* Main *)
begin
   WriteList(Filter(GetPrimes(ReadInt), @IsNotZero));
   {$ifdef windows}
      readln;
   {$endif}
end.

{$coperators on}
program crivo_eratosthenes;
 
function multiplo(mult, num : integer) : boolean;
(* Indica se MULT é um múltiplo de NUM *)
begin
     multiplo := (mult mod num = 0);
end;
 
procedure mostrar_primos(n : integer);
(* Calcula os primos e mostra-os *)
var lista : set of byte;  // Lista original, de 2 a N
    primos : set of byte; // Lista de primos, calculada
    i : integer;          // Número que será analisado
    j : integer;          // Contador
    l : integer;          // Auxiliar para determinar, após uma análise, qual o menor valor de LISTA
begin
     lista := [2..n]; // Define a lista original
     primos := [];    // Define que ainda não há primos calculados
     i:=2;            // A análise começa pelo número 2
     while ([i] <= lista) do begin
           primos += [i];           // I é um primo
           for j:=i to n do begin   // Elimina da LISTA os múltiplos de I
               if multiplo(j,i) then lista -= [j];
           end;
           l:=2;   // Determinação do menor valor actual da lista
           while (not ([l] <= lista)) and (l<=n) do l += 1;
           i := l; // Assim que determinado, é atribuído a I, que é primo.
     end;
     write('PRIMOS: ');   // Mostra os números primos calculados
     for i:=2 to n do begin
         if ([i] <= primos) then write(i,', ');
     end;
end;
 
var numero : integer;   // Limite de cálculo definido pelo utilizador
begin
     repeat
           write('Calcular numeros primos ate: ');
           readln(numero);
     until (numero in [2..maxint]); // só há números primos 1) positivos 2) maiores ou iguais a 2
                                    // [2..MAXINT] controla a introdução de um dado excessivamente grande
     writeln;
     mostrar_primos(numero);               // Calcula e mostra os números primos até NUMERO
     writeln;
     write('ENTER para sair...'); readln;  // Pausa antes de encerrar
end.

# DIM é o limite máximo dos primos
 
# Inicializar a lista com Verdadeiros
vals=[True]*DIM
 
# Os números 0 e 1 não são considerados primos
vals[0]=False
vals[1]=False
 
# Percorrer a lista à procura de um número primo
for i in range(2,DIM):
    # Se for primo, percorre-se toda a lista e tiram-se os múltiplos
    if vals[i]:
        for j in range(i*i,DIM,i):
            vals[j]=False
 
# Procurar os primos e fazer o output deles
for i in range(2,DIM):
    if vals[i]: print i,

>>> d = range(2, 20)
>>> [a for a in d if a not in [b for c in d for b in d if c != b and b%c==0]]
[2, 3, 5, 7, 11, 13, 17, 19]