Sobre o crivo de Eratóstenes - o crivo de primos mais antigo

O crivo de Eratóstenes encontra todos os números primos até um limite sem uma única divisão. Basta contar: risque um número em cada dois depois do 2, um em cada três depois do 3, e assim por diante. O que resta são os primos. Mais de dois mil anos depois, continua a ser uma das formas mais rápidas de os listar.

Experimentar o crivo de Eratóstenes
Uma grelha dos números de 1 a 100 com os múltiplos de 2, 3, 5 e 7 riscados em cores diferentes
Uma grelha dos números de 1 a 100 com os múltiplos de 2, 3, 5 e 7 riscados em cores diferentes

Eratóstenes de Cirene

Eratóstenes viveu aproximadamente entre 276 e 194 a.C. e dirigiu a grande biblioteca de Alexandria. É conhecido sobretudo por ter medido o tamanho da Terra a partir do comprimento das sombras em duas cidades. O crivo tem o seu nome porque Nicómaco de Gerasa o descreveu como o seu método na Introdução à Aritmética, escrita por volta do ano 100.

Como funciona o crivo

Escreva os números de 2 a N. O primeiro, 2, é primo: risque 4, 6, 8 e todos os outros múltiplos de 2. O número seguinte que resta, 3, é primo: risque 9, 12, 15 e assim por diante. Continue com 5, 7 e os números seguintes que restam. Um número que nunca é riscado não tem fator menor, por isso é primo.

Parar na raiz quadrada

Todo o número composto até N tem um fator primo que não é maior do que a raiz quadrada de N. Por isso, assim que p² é maior do que N, já não há nada para riscar. Para os primos até 100 só precisa de 2, 3, 5 e 7, e para 1000 dos primos até 31.

Quão rápido é?

O crivo precisa de cerca de N log log N passos, que crescem só um pouco mais depressa do que o próprio N. Os computadores ainda o usam, muitas vezes por partes num crivo segmentado, para listar primos até milhares de milhões. Para testar se um único número grande é primo, outros métodos são mais rápidos.

Perguntas frequentes

Quem inventou o crivo de Eratóstenes?

Tem o nome de Eratóstenes de Cirene, um sábio grego do século III a.C. A descrição escrita mais antiga é de Nicómaco de Gerasa, por volta do ano 100.

Porque é que o crivo começa a riscar em p²?

Cada múltiplo menor de p tem um fator primo menor, por isso um primo menor já o riscou.

Quantos primos há abaixo de 1000?

Há 168 primos abaixo de 1000. O maior é 997.

Ferramentas relacionadas

Exemplo de Crivo de Eratóstenes no PictorX

Crivo de Eratóstenes

Veja o crivo de Eratóstenes encontrar os números primos até 100, 200, 500 ou 1000. Cada primo risca os seus múltiplos com a sua própria cor, passo a passo.

 Exemplo de Espiral de Ulam no PictorX

Espiral de Ulam

Desenhe a espiral de Ulam no seu browser. Marque os primos, leia o polinómio quadrático de cada diagonal e abra a sequência ininterrupta de 40 primos de Euler.

 Espiral de Ulam dos primos, com a diagonal de Euler de quarenta primos traçada pelo centro

A espiral de Ulam

Como a espiral de Stanisław Ulam de 1963 dispõe os inteiros numa grelha quadrada, porque é que os primos se juntam em diagonais quadráticas e onde ficam os quarenta primos de Euler quando a espiral começa em 41.

 Exemplo de A conjetura de Collatz no PictorX

A conjetura de Collatz

Explore o problema de Collatz 3n+1 no seu navegador. Percorra sequências de granizo, faça crescer uma árvore de Collatz geométrica e aproxime o fractal de Collatz contínuo.

Pronto para experimentar?

Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.

Experimentar o crivo de Eratóstenes