Visualização do Crivo de Erastótenes

O crivo de Erastótenes continua sendo uma forma bastante eficiente de encontrar números primos, embora atualmente existam métodos melhores. Foi criado pelo matemático grego Erastótenes, que viveu cerca de 200 a.C.

A ideia é bastante simples.

Digamos, tenho uma lista de números de 1 a 20:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]

Pulo o 1, porque este divide todo mundo e até hoje há controvérsias se este deve ou não ser primo.

O próximo é o 2: e aí, risco todo mundo que é divisível por 2, daí para frente:
[1, 2, 3, 4, 5, 6, 7,8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]

O próximo não riscado é o 3: repito o procedimento e elimino todos os múltiplos de 3:

[1, 2, 3, 4, 5, 6, 7,8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]

Repito o processo até o fim, (ou melhor, até raiz(n)), e fico com a lista de números primos até n:

[2, 3, 5, 7, 11, 13, 17, 19]

O termo “crivo” é um sinônimo de “peneira”, e daí vem a ideia desta visualização. Eu queria ver o crivo como se fosse uma peneira mesmo: passa luz nos números primos, e não passa nos compostos.

Para tal, fiz uma rotinazinha em Javascript – D3, que pode ser acessada aqui:

https://asgunzi.github.io/CrivoErastotenesVisual/Index.html

Por exemplo, para n = 100 (um quadrado 10 x 10):

Destacando os primos:

[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]

Para n= 400 (20 x 20):

Para n= 900 (30 x 30):

Não sei bem se isso se parece um QR code dos números primos…

Algo a notar é que há várias colunas vazias (ex. as que são múltiplas de 2), enquanto as que terminam com 1, 3, 7 e 9 são mais cheias. Mas não tem um padrão muito claro – e essa falta de padrão dos primos vem atormentando os matemáticos há milênios!

Veja também:

https://asgunzi.github.io/CrivoErastotenesVisual/Index.html

Um comentário sobre “Visualização do Crivo de Erastótenes

Deixe um comentário

Faça o login usando um destes métodos para comentar:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair /  Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair /  Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair /  Alterar )

Conectando a %s