Matemática

Verificador de números primos (até 10.000.000)

Verifique instantaneamente se um inteiro N (até 10.000.000) é primo. Exibe os passos da divisão tentativa, o primo anterior e seguinte, e a fatoração.

Primeiros 100 números primos

#1–10 #2–11 #3–12 #4–13 #5–14 #6–15 #7–16 #8–17 #9–18 #10–19
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 101 103 107 109 113
127 131 137 139 149 151 157 163 167 173
179 181 191 193 197 199 211 223 227 229
233 239 241 251 257 263 269 271 277 281
283 293 307 311 313 317 331 337 347 349
353 359 367 373 379 383 389 397 401 409
419 421 431 433 439 443 449 457 461 463
467 479 487 491 499 503 509 521 523 541

Dicas

  • Um número primo é um inteiro maior que 1 sem divisores além de 1 e ele mesmo. A sequência começa com 2, 3, 5, 7, 11, 13, …
  • O teste de primalidade mais simples é a divisão tentativa: divida N por cada inteiro de 2 até √N. Se nenhum dividir exatamente, N é primo.
  • 1 não é primo. A definição de primo exige "maior que 1". O número 2 é o único primo par.
  • Existem infinitos números primos (provado por Euclides por volta de 300 a.C.). A densidade deles diminui com o tamanho — perto de n, aproximadamente 1 em cada ln(n) inteiros é primo (Teorema dos Números Primos).

Perguntas frequentes

2 não tem divisores além de 1 e ele mesmo, portanto é primo por definição. É também o único primo par — todos os outros números pares são divisíveis por 2.

A definição de primo exclui 1 ("um inteiro maior que 1"). Excluir 1 é necessário para que o Teorema Fundamental da Aritmética seja válido: se 1 fosse primo, as fatorações não seriam únicas (ex.: 6 = 2 × 3 = 1 × 2 × 3).

A divisão tentativa tem complexidade O(√N). Para N = 10.000.000, √N ≈ 3162, portanto são necessárias no máximo ~3162 divisões. Isso é suficientemente rápido para uso interativo.
ツールくん

Curiosidade — Por que os números primos são importantes

Os primos são os "átomos da aritmética". O Teorema Fundamental da Aritmética afirma que todo inteiro maior que 1 tem uma fatoração prima única — o que significa que os primos são os blocos irredutíveis de todos os números inteiros.

A moderna criptografia RSA — que protege o tráfego HTTPS e as assinaturas digitais — baseia-se em números primos. Multiplicar dois grandes primos é trivial; fatorar o produto de volta em primos é computacionalmente inviável, mesmo para supercomputadores modernos. Os primos sustentam a segurança da internet.

Mais ferramentas nesta categoria