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