Verificador de Número Primo

Primo é o número natural maior que 1 que tem exatamente dois divisores naturais: o 1 e ele mesmo. Os primeiros são 2, 3, 5, 7, 11, 13, 17, 19, 23 e 29. Quem tem algum outro divisor, como 15 = 3 × 5, é composto. O 2 é o único primo par, e a razão é quase tautológica: qualquer outro número par já tem o 2 como divisor além de 1 e de si mesmo, o que o torna composto de imediato. Essa singularidade faz do 2 uma exceção recorrente em demonstrações — é comum encontrar teoremas enunciados para "todo primo ímpar p" só para deixá-lo de fora. Os primos não seguem padrão visível de espaçamento. Entre 1 e 100 existem 25 deles; de 1 a 10 são quatro, mas entre 90 e 100 sobra apenas um, o 97.

Não é capricho de nomenclatura: incluir o 1 arruinaria o resultado mais importante da aritmética elementar. O Teorema Fundamental da Aritmética garante que todo inteiro maior que 1 se escreve como produto de primos de uma única maneira, a menos da ordem dos fatores. 12 = 2 × 2 × 3, e não existe outra decomposição. Se o 1 fosse primo, a unicidade evaporaria: 12 = 1 × 2 × 2 × 3 = 1 × 1 × 2 × 2 × 3, e assim por diante, infinitas fatorações diferentes para o mesmo número. Cada enunciado que depende da fatoração única — e são muitos — precisaria carregar a ressalva "sem contar os fatores 1". A classificação moderna resolve o problema com três categorias em vez de duas: o 1 não é primo nem composto, é uma unidade. O zero também fica de fora, por ser divisível por todos.

Para saber se um número n é primo, é suficiente procurar um divisor entre 2 e √n. Se nenhum dividir, n é primo. O argumento é curto. Se n é composto, existe uma escrita n = a × b com os dois fatores maiores que 1. Eles não podem ser ambos maiores que √n, porque então o produto ultrapassaria n. Logo, o menor deles é sempre menor ou igual a √n — e o teste o encontra antes de chegar lá. A economia é grande: para 997, em vez de quase mil divisões bastam as até 31, e ainda é possível pular todos os pares depois do 2. Uma otimização clássica testa apenas 2, 3 e os números da forma 6k ± 1, já que qualquer outro é múltiplo de 2 ou de 3. É essa a lógica do laço desta calculadora: a condição i × i ≤ n equivale a i ≤ √n sem precisar calcular raiz alguma.

A infinitude dos primos está demonstrada nos Elementos de Euclides e continua sendo um dos argumentos mais elegantes da matemática. Suponha uma lista finita contendo todos os primos. Multiplique todos e some 1. O número obtido não é divisível por nenhum primo da lista, porque sempre sobra resto 1. Então ou ele próprio é primo, ou tem um fator primo que não estava na lista — e nos dois casos a lista era incompleta. Como o raciocínio vale para qualquer lista finita, nenhuma lista finita dá conta. Infinitos, sim, mas cada vez mais espaçados. O teorema dos números primos descreve essa rarefação: perto de um número n, a proporção de primos é da ordem de 1 ÷ ln(n). Na vizinhança de mil isso dá cerca de um em sete; na de um milhão, cerca de um em quatorze. Para listar todos os primos até um limite, o método mais direto continua sendo o crivo de Eratóstenes: escreva os números, risque os múltiplos de 2, depois os de 3, e siga; o que sobra é primo.

Os primos são os átomos dos inteiros: pela fatoração única, todo número é um produto deles e de mais nada. Daí saem ferramentas do dia a dia — o MDC é o produto dos fatores comuns com o menor expoente, o MMC é o de todos os fatores com o maior expoente, e simplificar fração é cancelar fatores primos repetidos. O uso mais visível hoje é a criptografia. Multiplicar dois primos enormes é instantâneo; recuperar os fatores a partir do produto, com números de centenas de dígitos, é computacionalmente caríssimo. O sistema RSA vive dessa assimetria. E sobram perguntas simples sem resposta. Não se sabe se há infinitos primos gêmeos — pares como 11 e 13 ou 17 e 19, separados por 2. Nem se todo par maior que 2 é a soma de dois primos, a conjectura de Goldbach. Os maiores primos hoje conhecidos são da forma 2^p − 1, os primos de Mersenne.