numbers Lista e Verificador de Números Primos star

Como Funciona

A ferramenta alterna entre dois algoritmos diferentes, cada um adequado a uma pergunta diferente. O modo de listagem encontra todos os primos até um limite usando o Crivo de Eratóstenes, um dos algoritmos mais antigos ainda em uso cotidiano (atribuído ao matemático grego Eratóstenes, século III a.C.). Começando do 2, ele marca todo múltiplo de 2 como composto, depois passa para o próximo número não marcado (3) e marca todos os seus múltiplos, depois o próximo não marcado (5), e assim por diante. Tudo o que sobrar sem marcação ao chegar à raiz quadrada do limite é primo. Um exemplo pequeno: para peneirar até 30, risque os múltiplos de 2 (4, 6, 8, …), depois os múltiplos de 3 (6, 9, 12, …, alguns já riscados), depois os múltiplos de 5 (10, 15, …) — como 5×5=25 ≤ 30 mas 7×7=49 > 30, você pode parar aí; o que restar — 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 — é a lista completa. Isso roda em tempo O(n log log n), ou seja, continua rápido mesmo quando o intervalo cresce até centenas de milhares.

O modo de verificação responde a uma pergunta diferente — este número específico é primo? — usando divisão por tentativa até a raiz quadrada. Para testar se n é primo, basta verificar divisores de 2 até √n. O raciocínio: se n = a × b com a e b maiores que √n, então a × b seria maior que n, o que é impossível. Então pelo menos um dos dois fatores deve ser √n ou menor, e ele será encontrado antes que o laço termine. Exemplo: para verificar 97, basta testar a divisibilidade por 2, 3, 5, 7 (já que 9² = 81 ≤ 97 mas 10² = 100 > 97) — nenhum divide exatamente, então 97 é primo.

O Que Saber

Os dois modos existem porque compensam de formas diferentes: o crivo é eficiente para produzir muitos primos de uma vez, mas desperdiça memória e tempo se você só se importa com um número perto de um limite enorme; a divisão por tentativa é eficiente para uma única verificação, mas fica lenta demais se repetida para cada número de um intervalo grande, um de cada vez. Escolher a opção certa para a tarefa é exatamente por isso que esta ferramenta oferece as duas.

• O 1 é excluído dos primos por definição e convenção — ele tem apenas um divisor, não dois, o que quebraria a unicidade da fatoração em primos se fosse permitido.
• O 2 é o único primo par; todos os outros números pares são divisíveis por 2 e, portanto, compostos.
• À medida que os números crescem, os primos ficam mais raros em média, mas nunca param de aparecer — Euclides provou há mais de dois mil anos que existem infinitos primos.