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 não riscado é o 3: repito o procedimento e elimino todos os múltiplos de 3:
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:
Originally published at https://ideiasesquecidas.com on April 17, 2022.
