Números primos
Verifique na hora se um número é primo (e descubra o menor divisor dele, se não for), ou gere a lista completa de números primos até 100.000.
Como verificar se um número é primo
Um número é primo quando tem exatamente dois divisores: 1 e ele mesmo. Para testá-lo não é preciso tentar todos os números, basta procurar divisores até a raiz quadrada, porque se n = a × b, pelo menos um dos dois fatores precisa ser ≤ √n. Esta ferramenta testa o 2 e o 3 e depois só os candidatos da forma 6k ± 1 (os únicos primos possíveis além do 3), então a verificação é instantânea mesmo para números de até um trilhão. Quando o número não é primo, o menor divisor encontrado é sempre, ele próprio, um número primo.
O Crivo de Eratóstenes, um algoritmo de 2.200 anos
A lista é gerada com o método do matemático grego Eratóstenes: escreva todos os números até o limite e depois “peneire” os múltiplos de cada primo que encontrar, começando pelo quadrado dele. O que sobrar é primo. Os primos ficam mais raros à medida que os números crescem: existem 25 abaixo de 100, 168 abaixo de 1.000 e 9.592 abaixo de 100.000 e, mesmo assim, como Euclides provou, eles nunca acabam.