O que é um número primo
Número primo é todo número natural maior que 1 que só pode ser dividido exatamente por 1 e porele mesmo. Os que têm outros divisores são chamados de compostos: 15 é composto porque 15 = 3 × 5. Os números 0 e 1 não são nem primos nem compostos.
Os primos até 100 são 25:
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
Como verificar se um número é primo
- Se o número for par e diferente de 2, ele não é primo.
- Calcule a raiz quadrada do número (não precisa ser exata).
- Divida o número por cada primo de 2 até essa raiz.
- Se alguma divisão for exata, o número é composto. Se nenhuma for, ele é primo.
Por que parar na raiz quadrada? Se n = a × b e os dois fatores fossem maiores que √n, o produto passaria de n. Então todo número composto tem pelo menos um divisor menor ou igual à sua raiz.
Exemplos
97 é primo?
√97 ≈ 9,85. Testamos os primos 2, 3, 5 e 7: 97 é ímpar, a soma dos algarismos (16) não é múltiplo de 3, não termina em 0 nem 5, e 97 ÷ 7 = 13,86. Nenhuma divisão exata: 97 é primo.
91 é primo?
Parece, mas não é. √91 ≈ 9,54. Passa por 2, 3 e 5, mas 91 ÷ 7 = 13, exato. Logo 91 = 7 × 13 é composto. É uma pegadinha comum em provas e concursos.
Critérios de divisibilidade que ajudam
| Divisor | Regra | Exemplo |
|---|---|---|
| 2 | Termina em 0, 2, 4, 6 ou 8 | 1.358 |
| 3 | A soma dos algarismos é múltiplo de 3 | 471 (4 + 7 + 1 = 12) |
| 5 | Termina em 0 ou 5 | 2.035 |
| 7 | Tire o dobro do último algarismo do número formado pelos demais; o resultado deve ser múltiplo de 7 | 203: 20 − 2 × 3 = 14 |
| 11 | A soma alternada dos algarismos (+ − + …) é múltiplo de 11 | 2.728: 8 − 2 + 7 − 2 = 11 |
E números muito grandes?
Para números com muitos algarismos, testar todos os primos até a raiz levaria tempo demais. A calculadora usa então o teste de Miller–Rabin, que verifica propriedades das potências do número em vez de dividir por cada primo. Com as bases 2, 3, 5, …, 37, o teste é comprovadamente exato para todos os números com até 24 algarismos, e aqui o limite é de 18. Quando o número é composto, ela encontra os fatores pelo método rho de Pollard.
É justamente essa assimetria que torna os primos tão úteis na criptografia: multiplicar dois primos gigantes é fácil, mas descobrir quais foram multiplicados, a partir do produto, é praticamente impossível. Sistemas como o RSA, usado em certificados digitais, dependem disso.
Para decompor um número em fatores primos com o dispositivo prático da “barra”, use acalculadora de fatoração. Para listar todos os divisores, use acalculadora de divisores.