Ir para o conteúdo
thoga31

[Snippet | Desafio] Crivo de Eratosthenes

Mensagens Recomendadas

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! | Occasional Fortnite player

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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.

  • Voto 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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
KTachyon

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

  • Voto 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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora

×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade. Este site usa cookies para disponibilizar funcionalidades personalizadas. Para mais informações visite esta página.