Gerador do Crivo de Eratóstenes (Grátis) – Lista de primos e o N-ésimo primo
Insira um limite superior N para gerar uma lista de números primos usando o Crivo de Eratóstenes, visualizado passo a passo. Também permite buscar o N-ésimo primo (até o 1.000.000º) — grátis, no navegador, sem cadastro.
Crivo de Eratóstenes de 1 a 100 (tabela de referência)
As células verdes são números primos; o restante foi eliminado pelo crivo.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
| 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 |
| 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 |
| 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 |
| 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 |
| 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 |
| 71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 |
| 81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 |
| 91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 |
1 não é primo nem composto, por isso não é colorido.
O que faz o crivo de Eratóstenes
O crivo de Eratóstenes é o algoritmo clássico para encontrar números primos, que deve o nome ao sábio grego do século III a. C. A ideia é espantosamente simples: tome cada número por ordem a partir do dois, declare-o primo se ainda não tiver sido riscado e risque em seguida todos os seus múltiplos. Risque os múltiplos de dois, depois os do três que sobreviveu, a seguir os do cinco; repita até à raiz quadrada do seu limite e todo o número que continuar de pé será primo.
Indique a esta ferramenta um limite superior e ela gera a lista de primos até um milhão. Mostra o processo de riscar passo a passo, pelo que pode seguir com os seus próprios olhos que primo eliminou que números. Também funciona ao contrário e responde à pergunta «qual é o primo número N?» para posições tão altas como a milionésima. Tudo é calculado no seu navegador, por isso nada do que introduzir sai dele.
Como gerar uma lista de primos
- Introduza o limite superior N Indique um inteiro entre 2 e 1.000.000. Começar por algo pequeno como 100 torna bem mais visível o mecanismo do crivo.
- Verifique a contagem e o maior primo Obtém quantos primos existem até N — escrito π(N) — e o maior deles.
- Siga os passos do riscar Com limites pequenos, cada etapa mostra que primo foi usado e que números eliminou.
- Procure o primo número N Introduza uma posição e a ferramenta devolve o primo que a ocupa.
Dicas para aproveitar melhor
- O Crivo de Eratóstenes lista com eficiência todos os primos até N riscando os múltiplos de cada primo encontrado, começando pelo 2.
- Defina o limite superior N como 400 ou menos para ver exatamente qual primo eliminou qual número, passo a passo.
- A busca do N-ésimo primo aceita consultas como "qual é o primo de número 1.000.000", útil para confirmar a existência de primos muito grandes.
- Tudo roda localmente no seu navegador — a lista de primos gerada nunca é enviada a um servidor.
Situações em que ajuda
Estudar algoritmos
O crivo é o exemplo de manual da complexidade O(n log log n), e vê-lo correr fixa a ideia.
Verificar a sua própria implementação
Compare a saída de um crivo escrito por si com esta para confirmar que produz a sequência correta.
Observar como se distribuem os primos
Variar o limite e observar como cresce π(N) dá ideia do teorema dos números primos e do seu comportamento aproximado N / log N.
Documentar-se sobre criptografia
Os esquemas de chave pública como o RSA assentam em primos grandes, e esta é uma via de entrada para perceber com que densidade surgem.
Termos de primos e crivos
- Número primo
- Um número natural maior ou igual a dois cujos únicos divisores positivos são o um e ele próprio. O um não conta como primo.
- Número composto
- Um número natural maior ou igual a dois que não é primo. São estes que o crivo vai riscando.
- π(N)
- A função que dá a contagem de primos até N, conhecida como função de contagem de primos.
- Riscar
- Marcar os múltiplos de um primo para os excluir dos candidatos. É a operação que dá nome ao algoritmo.
- Porque basta a raiz quadrada
- Todo o múltiplo de um primo maior do que a raiz quadrada de N já foi riscado como múltiplo de algum primo menor.
- Teorema dos números primos
- O resultado segundo o qual π(N) é assintótica a N / log N, que descreve com que rapidez os primos rareiam.
Perguntas frequentes
Curiosidade — Por que um algoritmo de 2.000 anos ainda é usado
O Crivo de Eratóstenes é um dos algoritmos geradores de primos mais antigos ainda existentes, atribuído ao erudito grego Eratóstenes, que foi bibliotecário-chefe da Biblioteca de Alexandria no século III a.C. O fato de um método concebido há mais de dois mil anos ainda ser ensinado em cursos de ciência da computação hoje mostra sua elegante simplicidade.
O mecanismo é surpreendentemente simples: lista-se os inteiros a partir de 2, toma-se o menor número ainda não marcado como primo, e riscam-se todos os seus múltiplos. Repetindo isso até √N, todos os primos até N são revelados. Para gerar uma lista completa de primos, isso é muito mais eficiente do que testar cada número individualmente por divisão tentativa.
A busca por primos enormes continua até hoje — projetos de computação distribuída como o GIMPS (Great Internet Mersenne Prime Search) seguem descobrindo primos de Mersenne com dezenas de milhões de dígitos. O crivo em si não é usado para encontrar primos tão grandes, mas sua ideia central — eliminar múltiplos mecanicamente — fundamenta algoritmos mais avançados de teste de primalidade.