Crivo de Eratosthenes/Eratóstenes
O Crivo de Eratosthenes é um algoritmo que nos permite obter o conjunto dos números primos menores de que um determinado valor.
Explicação do Algoritmo
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 é, removem-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.
Visualização do crivo
Implementação
C
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;
}
C (Eratosthenes + Euler)
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.
Haskell
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]
Pascal / Delphi
Apresentam-se duas formas de implementar o Crivo com variação dos tipos de dados utilizados.
Uso de open arrays
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.
Uso de conjuntos (sets)
{$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.
Python
Implementação semelhante à apresentada em C
# 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,
Implementação recorrendo a listas por compreensão
>>> 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]