Calculadora de Números Primos

Número primo é o número natural maior que 1 que tem exatamente dois divisores: o 1 e ele mesmo. Os primeiros são 2, 3, 5, 7, 11, 13, 17, 19, 23 e 29. Os demais números maiores que 1, com mais de dois divisores, são chamados de compostos.

O 1 não é primo, porque tem um único divisor, ele mesmo. Ele também não é composto. O 2 é o único primo par: todo outro número par é divisível por 2 e, portanto, composto.

Há 25 números primos entre 1 e 100:

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

E a quantidade de primos até cada potência de 10:

Os primos ficam mais raros conforme os números crescem, mas nunca acabam: o matemático grego Euclides provou, há mais de dois mil anos, que existem infinitos números primos.

O método direto é tentar dividir o número pelos primos menores que ele. O atalho é parar na raiz quadrada: se um número composto n = a × b, pelo menos um dos fatores é menor ou igual a √n. Então, se nenhum primo até √n divide n, ele é primo.

basta testar os primos p com p × p ≤ n

Exemplo: 97. A raiz de 97 é cerca de 9,8, então basta testar 2, 3, 5 e 7. Nenhum divide 97 (os restos são 1, 1, 2 e 6), e o 97 é primo. Já o 91 parece primo, mas 91 = 7 × 13.

As regras de divisibilidade ajudam a descartar rápido:

Eratóstenes, matemático grego, criou um método para achar todos os primos até um limite. Escreva os números de 2 até o limite e repita:

• pegue o menor número que ainda não foi riscado: ele é primo;
• risque todos os múltiplos dele, a partir do quadrado dele;
• repita até passar da raiz quadrada do limite.

O que sobra sem risco são os primos. É o método que a aba Lista de primos usa para listar até 100.000.

Todo número maior que 1 pode ser escrito, de um único jeito, como produto de primos. Para fatorar, divida o número pelo menor primo possível, repetidamente, até chegar em 1.

Exemplo: 360. 360 ÷ 2 = 180, ÷ 2 = 90, ÷ 2 = 45; depois 45 ÷ 3 = 15, ÷ 3 = 5; e 5 é primo. Então:

360 = 2³ × 3² × 5

Da fatoração sai a quantidade de divisores: some 1 a cada expoente e multiplique. Em 360, (3 + 1) × (2 + 1) × (1 + 1) = 24 divisores. A fatoração também é o caminho mais seguro para o MMC e o MDC.

• Primos gêmeos são primos que diferem por 2, como 3 e 5, 11 e 13, ou 17 e 19.
• 2 e 3 são os únicos primos seguidos. Em qualquer outro par de números consecutivos, um deles é par e maior que 2, portanto composto.
• Criptografia: a segurança de sistemas como o RSA usa o fato de ser fácil multiplicar dois primos enormes e muito difícil fazer o caminho inverso, a fatoração.

• Achar que o 1 é primo. Ele só tem um divisor.
• Achar que todo número ímpar é primo. 9, 15, 21 e 91 são ímpares e compostos.
• Esquecer que o 2 é primo. É o único par que é primo.
• Testar divisores só até a metade. Não precisa: a raiz quadrada basta.