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