Entendendo os resultados
A tabela abaixo mostra as três saídas para algumas entradas de exemplo.
| Entrada | É primo? | Fatoração | Próximo primo |
|---|---|---|---|
| 97 | Sim | 97 | 101 |
| 84 | Não | 2 x 2 x 3 x 7 | 89 |
| 100 | Não | 2 x 2 x 5 x 5 | 101 |
| 2 | Sim (único primo par) | 2 | 3 |
| 1 | Não (nem primo nem composto) | - | 2 |
- O número 1 não é primo: primos precisam ter exatamente dois divisores distintos, e o 1 tem apenas um. Excluir o 1 preserva a unicidade da fatoração em primos.
- A divisão por tentativa é exata, mas fica lenta para entradas muito grandes; esta calculadora aceita números de até 10^12, caso em que a busca testa divisores até um milhão.
- A busca pelo próximo primo termina rapidamente nesse intervalo: pelo postulado de Bertrand, sempre existe um primo entre n e 2n.
O que é um número primo?
Um número primo é um número natural maior que 1 que tem exatamente dois divisores positivos: 1 e ele mesmo. Os primeiros primos são 2, 3, 5, 7, 11, 13, 17, 19, 23 e 29. O número 2 é o único primo par, já que todos os demais números pares são divisíveis por 2. Números maiores que 1 que não são primos chamam-se compostos; o número 1, por definição, não é nem primo nem composto.
O teorema fundamental da aritmética afirma que todo inteiro maior que 1 pode ser escrito como produto de primos de exatamente uma maneira, salvo pela ordem dos fatores. É essa fatoração única em primos que faz dos primos os blocos de construção dos inteiros: 84 = 2^2 x 3 x 7, e nenhuma outra combinação de primos resulta em 84.
Os primos são infinitos — resultado demonstrado por Euclides por volta de 300 a.C. — e vão ficando mais raros conforme os números crescem, embora sem nenhum padrão simples. Primos grandes sustentam a criptografia moderna de chave pública (como o RSA), que se apoia na dificuldade prática de fatorar o produto de dois primos muito grandes.
Como usar esta calculadora de números primos
- Informe um número inteiro n de pelo menos 1. Decimais são arredondados para baixo até o inteiro mais próximo.
- Leia o veredito de primalidade: um sinal de confirmação indica que o número é primo, e um sinal de negação indica que ele é composto (ou 1, que não é nenhum dos dois).
- Leia a fatoração em primos — o produto único de primos igual ao seu número. Para uma entrada prima, a fatoração é o próprio número.
- Leia o próximo primo, o menor primo estritamente maior que o seu número.
Como a primalidade é testada: divisão por tentativa
Um número n é composto se, e somente se, tiver um divisor maior que 1 e no máximo igual à raiz quadrada de n. Isso acontece porque os divisores vêm aos pares: se n = a x b com a <= b, então a <= √n. Portanto, a divisão por tentativa só precisa testar candidatos a divisor até √n — e, depois de checar o 2, bastam os candidatos ímpares.
Exemplo resolvido (primo): n = 97. A raiz quadrada de 97 é cerca de 9,85, portanto basta testar 2, 3, 5, 7 e 9. O 97 é ímpar; 9 + 7 = 16 não é divisível por 3; ele não termina em 0 nem em 5; 97 / 7 = 13,857...; e 97 / 9 não é inteiro. Não existe divisor, logo 97 é primo.
Exemplo resolvido (fatoração): n = 84. Vá dividindo pelos primos, do menor para o maior: 84 / 2 = 42, 42 / 2 = 21, 21 / 3 = 7, e 7 é primo. Portanto 84 = 2 x 2 x 3 x 7 = 2^2 x 3 x 7. O próximo primo depois de 84 é 89 (85 = 5 x 17, 86 = 2 x 43, 87 = 3 x 29, 88 = 2^3 x 11).
Erros comuns
- Contar o 1 como número primo — por definição, um primo tem exatamente dois divisores distintos, e o 1 tem apenas um.
- Supor que todos os primos são ímpares: o 2 é primo, e é o único primo par.
- Testar divisores até n em vez de parar em √n — todo número composto tem um fator igual ou inferior à sua raiz quadrada.
- Acreditar que todo número ímpar é primo: 9 = 3 x 3, 15 = 3 x 5 e 21 = 3 x 7 são ímpares compostos.
- Confundir fatoração em primos com qualquer fatoração: 84 = 4 x 21 é uma fatoração, mas a fatoração em primos é 2 x 2 x 3 x 7.
Perguntas frequentes
Como verificar se um número é primo?
Teste se algum inteiro de 2 até a raiz quadrada do número o divide exatamente. Se nenhum dividir, o número é primo. Para 97, a raiz quadrada é cerca de 9,85, e nenhum entre 2, 3, 5, 7 e 9 divide 97, portanto 97 é primo. Os pares de divisores garantem que todo número composto tem um fator igual ou inferior à sua raiz quadrada.
Por que o 1 não é um número primo?
Um primo é definido como tendo exatamente dois divisores positivos distintos, 1 e ele mesmo; o número 1 tem apenas um divisor. A definição também protege o teorema fundamental da aritmética: se o 1 fosse primo, as fatorações deixariam de ser únicas (6 = 2 x 3 = 1 x 2 x 3 = 1 x 1 x 2 x 3, e assim por diante).
O que é uma fatoração em primos?
É a expressão de um número como produto de números primos, que o teorema fundamental da aritmética garante ser única salvo pela ordem. Por exemplo, 84 = 2 x 2 x 3 x 7. Para encontrá-la, divida repetidamente pelo menor primo que couber exatamente, até que o quociente restante seja 1 ou primo.
O 2 é um número primo?
Sim — o 2 é primo porque seus únicos divisores são 1 e 2, e é o único primo par. Todos os demais números pares são divisíveis por 2 e, portanto, compostos. É por isso que os testes de primalidade tratam o 2 à parte e depois verificam apenas candidatos ímpares.
Quantos números primos existem?
Infinitos, como Euclides demonstrou por volta de 300 a.C.: dada qualquer lista finita de primos, o número formado multiplicando todos eles e somando 1 não é divisível por nenhum, portanto algum primo ficou de fora da lista. Os primos rareiam conforme os números crescem — pelo teorema dos números primos, a densidade de primos perto de n é da ordem de 1 / ln(n) — mas nunca se esgotam.
Por que os números primos importam na criptografia?
Sistemas de chave pública como o RSA se apoiam numa assimetria: multiplicar dois primos grandes é fácil, mas recuperar os primos a partir do produto é computacionalmente difícil nos tamanhos usados na prática (centenas de dígitos). As chaves de segurança são construídas a partir desses produtos, o que torna a geração de primos e os testes de primalidade operações criptográficas centrais.
Referências
- Weisstein, Eric W. "Prime Number" and "Fundamental Theorem of Arithmetic." MathWorld — A Wolfram Web Resource. mathworld.wolfram.com.
- Hardy GH, Wright EM. An Introduction to the Theory of Numbers. Oxford University Press (primes, unique factorization, Bertrand's postulate).
- Euclid. Elements, Book IX, Proposition 20 (infinitude of primes).