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); |
> |