crivo.mws

Crivo de Eratostenes

Procedimento que lista todos os primos desde 1 até um dado inteiro n

11/10/2007

Definição do procedimento crivo

>    crivo := proc(n)

>       local i,j,          #indices do ciclo

>             isPrime,      #array de booleanos

>             lista_primos, #lista de primos

>             sqrtn;        #aprox. inteira de sqrt(n)

>       #inicializa array

>       isPrime := table();

>       isPrime[1] := false;

>       for i from 2 to n do

>           isPrime[i] := true

>       od;

>       #obtem aprox. inteira da raiz quadrada do argumento n

>       #adiciona 1 por segurança

>       sqrtn := 1 + isqrt(n);

>       #o crivo

>       for i from 1 to sqrtn do

>           #salta se não for primo

>           if isPrime[i] then

>              for j from i+1 to n do

>                  #testa se i divide j

>                  if type(j/i,integer) then

>                     isPrime[j] := false

>                  fi;

>              od;

>           fi;

>       od;

>       #converte a lista de booleanos numa lista de primos

>       lista_primos := NULL;

>       for i from 1 to n do

>             if isPrime[i] then

>                 lista_primos := lista_primos, i;

>             fi;

>       od;

>       RETURN(lista_primos);

>     end;

Listagem dos primos até 1000

>    crivo(1000);

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, ...
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, ...
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, ...
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, ...
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, ...

>