Jump to content
Sign in to follow this  
thoga31

[Snippet | Desafio] Crivo de Eratosthenes

Recommended Posts

thoga31

Este já eu o fiz há uns tempos.

Decidi resolver com um dos algoritmos mais elegantes para Pascal: recorri a conjuntos.

program crivo_eratosthenes;
(*
Calcula os números primos de 2 até N
recorrendo ao Crivo de Eratosthenes.
*)
uses crt;
var numero : integer; // Limite de cálculo definido pelo utilizador

function multiplo(mult, num : integer) : boolean;
(* Indica se MULT é um múltiplo de NUM *)
begin
     if (mult mod num = 0) then multiplo := true
     // Se é múltiplo, o resto da divisão (MOD) é zero
     else multiplo := false;
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;

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.

Para mais informações, têm o seguinte documento da Wiki: http://wiki.portugal-a-programar.org/dev_geral:pascal:snippet:eratosthenes

(é um redireccionamento para o documento original)

O meu desafio é o seguinte: tentem implementar o Crivo sem recorrer a conjuntos, que é a forma de seguir de forma mais natural cada passo deste.

Será muito interessante ter várias propostas de resolução na Wiki. Contribuam! :thumbsup:


Knowledge is free!

Share this post


Link to post
Share on other sites
KTachyon

Se assumires automaticamente que o 2 e o 3 são primos, consegues desenvolver um crivo de duas colunas que representam o numero anterior e o número seguinte dos múltiplos de 6. Os saltos vão funcionar da mesma forma que fazes no crivo linear e, portanto, tens que fazer menos cálculos e precisas de menos memória.

Tem uma outra vantagem... como os resultados nas duas colunas são independentes (podes consultar logo a segunda coluna e ver que saltos precisas de fazer), é possível, com alguma sincronização, colocares dois threads a realizar os cálculos.

Achar os primeiros 50 milhões de primos é uma questão de poucos segundos com 300MB de memória, se utilizares chars. Com bits consegues reduzir o valor de memória necessário para 40MB, mas eu não consegui que fosse mais eficiente em termos de tempo. Tenho isto feito em C.

  • Vote 1

“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”

-- Tony Hoare

Share this post


Link to post
Share on other sites
KTachyon

Deixei na wiki a minha versão do crivo com o teorema de Euler para quem quiser portar para as restantes linguagens.

  • Vote 1

“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”

-- Tony Hoare

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.