Calculadora de Fatoração em Números Primos

Fatoração em números primos (decomposição em primos) expressa um inteiro positivo como um produto de números primos. Todo inteiro > 1 tem uma fatoração em primos única (Teorema Fundamental da Aritmética). Exemplo: 360 = 2³ × 3² × 5. Passos: encontre o menor fator primo, divida, repita até que o quociente seja 1. Algoritmo: divisão por tentativa de primos até √n. Eficiente para números até ~10^12; números maiores requerem algoritmos avançados (rho de Pollard, peneira de corpos de números). Fatoração em números primos é computacionalmente difícil para números muito grandes — essa dificuldade sustenta a criptografia RSA.

Criptografia: RSA e outros sistemas de chave pública dependem da dificuldade de fatorar números grandes. Calcular MDC/MMC: MDC(a,b) = produto dos fatores primos comuns com expoentes mínimos. MMC(a,b) = produto de todos os fatores primos com expoentes máximos. Simplificação de frações: divida numerador e denominador por MDC. Função totiente de Euler: φ(n) = n × ∏(1 - 1/p) para cada fator primo distinto p. Determinando quadrados perfeitos: n é um quadrado perfeito se todos os expoentes dos fatores primos são pares. Número de divisores: (e₁+1)(e₂+1)...(eₖ+1) onde eᵢ são os expoentes.

A Peneira de Eratóstenes encontra eficientemente todos os primos até N. Algoritmo: crie um array booleano [2..N], marque todos como verdadeiro. Para cada número não marcado p começando de 2: marque todos os múltiplos de p (p², p²+p, ...) como compostos. Os números não marcados restantes são primos. Tempo: O(n log log n), Espaço: O(n). Otimizações: comece a marcar em p² (múltiplos menores já foram marcados), apenas verifique números ímpares após 2. Para N = 10^6: ~78.498 primos. Para N = 10^9: precisa de peneira segmentada para reduzir memória. Usada em programação competitiva e pesquisa de teoria dos números.

A função totiente de Euler φ(n) conta os inteiros de 1 a n que são coprimos (não compartilham fatores comuns) com n. Propriedades-chave: φ(1) = 1. Para um primo p: φ(p) = p − 1. Para uma potência prima: φ(p^k) = p^k − p^(k-1). Para a, b coprimos: φ(a×b) = φ(a)×φ(b) (multiplicativa). Geral: φ(n) = n × ∏(1 − 1/p) para cada primo distinto p dividindo n. Exemplo: φ(12) = 12 × (1−1/2) × (1−1/3) = 12 × 1/2 × 2/3 = 4. Inteiros coprimos com 12: {1, 5, 7, 11}. Usada em: RSA (Teorema de Euler: a^φ(n) ≡ 1 mod n), teoria de grupos.

Um número perfeito é igual à soma de seus divisores próprios (divisores excluindo ele mesmo). Exemplos: 6 = 1+2+3. 28 = 1+2+4+7+14. 496. 8128. Apenas 51 números perfeitos são conhecidos; todos os conhecidos são pares. Primos de Mersenne: n = 2^(p-1) × (2^p - 1) é perfeito quando (2^p - 1) é primo (primo de Mersenne). Conceitos relacionados: Número abundante: σ(n) > 2n (soma de todos os divisores > 2×número). Número deficiente: σ(n) < 2n. Números amigáveis: par onde σ(a) = b+a e σ(b) = a+b. Exemplo: 220 e 284.