Números Primos
Verifique se um número é primo ou gere a lista completa de primos até 100.000 com o Crivo de Eratóstenes.
O que é um número primo?
Um número primo é um inteiro maior que 1 que possui exatamente dois divisores: 1 e ele mesmo.
- 2 é primo (divisores: 1, 2)
- 17 é primo (divisores: 1, 17)
- 15 não é primo (divisores: 1, 3, 5, 15)
Os primeiros primos: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37…
Por que 1 não é primo?
Por definição formal. A definição rigorosa de número primo exige exatamente dois divisores distintos. O número 1 tem apenas um divisor (ele mesmo), então não satisfaz a condição.
Há também uma razão prática: se 1 fosse primo, o Teorema Fundamental da Aritmética (todo inteiro > 1 se decompõe em primos de forma única) perderia validade, pois 6 = 2 × 3 = 1 × 2 × 3 = 1 × 1 × 2 × 3 seriam decomposições diferentes.
Crivo de Eratóstenes
O Crivo de Eratóstenes é um algoritmo da Grécia Antiga (~240 a.C.) para encontrar todos os primos até N:
- Liste todos os números de 2 até N
- Marque 2 como primo; risque todos os múltiplos de 2
- Vá para o próximo número não riscado (3); risque seus múltiplos
- Repita até
√N - Todos os números não riscados são primos
A eficiência é O(N log log N) — muito rápida para N ≤ 100.000.
Números primos na criptografia
O RSA (o algoritmo de criptografia mais usado no mundo para TLS/HTTPS) baseia-se na dificuldade de fatorar o produto de dois números primos grandes:
n = p × q (p e q são primos gigantes, centenas de dígitos)É fácil calcular n a partir de p e q, mas praticamente impossível recuperar p e q a partir de n — esse é o trapdoor matemático do RSA.
Os maiores números primos conhecidos (primos de Mersenne) têm dezenas de milhões de dígitos.
Curiosidades
- 2 é o único número primo par — todos os outros são ímpares
- Existem infinitos primos (Euclides provou isso ~300 a.C.)
- Conjectura de Goldbach (1742): todo número par > 2 é a soma de dois primos — ainda não provada
- Primos gêmeos: pares de primos com diferença 2 (ex: 11 e 13, 17 e 19) — provavelmente infinitos, mas não provado
Perguntas frequentes
Como verifico se um número grande é primo rapidamente?
Esta ferramenta usa divisibilidade por teste até √N. Para números muito grandes (centenas de dígitos), usa-se o Teste de Miller-Rabin, um algoritmo probabilístico amplamente usado em criptografia.
Quantos primos existem até 100.000?
9.592 primos. Até 1.000: 168 primos. Até 1.000.000: 78.498 primos. A densidade de primos diminui conforme os números crescem (Teorema dos Números Primos).
Por que alguns números são chamados “quase-primos”?
Números com apenas dois fatores primos (não necessariamente distintos) são chamados semiprimos ou biprimos — ex: 4 = 2², 6 = 2×3, 15 = 3×5. São importantes na criptografia RSA.