Calculadora de factorización prima

La factorización en primos (descomposición en factores primos) expresa un entero positivo como un producto de números primos. Todo entero > 1 tiene una factorización en primos única (Teorema Fundamental de la Aritmética). Ejemplo: 360 = 2³ × 3² × 5. Pasos: encuentre el factor primo más pequeño, divida, repita hasta que el cociente sea 1. Algoritmo: división de prueba por primos hasta √n. Eficiente para números hasta ~10^12; los números más grandes requieren algoritmos avanzados (rho de Pollard, criba del cuerpo numérico). La factorización en primos es computacionalmente difícil para números muy grandes — esta dificultad sustenta la criptografía RSA.

Criptografía: RSA y otros sistemas de clave pública se basan en la dificultad de factorizar números grandes. Cálculo de MCD/MCM: MCD(a,b) = producto de factores primos comunes con exponentes mínimos. MCM(a,b) = producto de todos los factores primos con exponentes máximos. Simplificación de fracciones: divida numerador y denominador entre el MCD. Función phi de Euler: φ(n) = n × ∏(1 - 1/p) para cada factor primo p distinto. Determinar cuadrados perfectos: n es un cuadrado perfecto si todos los exponentes de factores primos son pares. Número de divisores: (e₁+1)(e₂+1)...(eₖ+1) donde eᵢ son los exponentes.

La Criba de Eratóstenes encuentra eficientemente todos los primos hasta N. Algoritmo: cree un array booleano [2..N], marque todo como verdadero. Para cada número no marcado p comenzando desde 2: marque todos los múltiplos de p (p², p²+p, ...) como compuesto. Los números no marcados restantes son primos. Tiempo: O(n log log n), Espacio: O(n). Optimizaciones: comience a marcar en p² (los múltiplos menores ya están marcados), verifique solo números impares después del 2. Para N = 10^6: ~78.498 primos. Para N = 10^9: se necesita una criba segmentada para reducir la memoria. Se usa en programación competitiva e investigación de teoría de números.

La función phi de Euler φ(n) cuenta los enteros del 1 al n que son coprimos (no comparten factores comunes) con n. Propiedades clave: φ(1) = 1. Para primo p: φ(p) = p − 1. Para potencia prima: φ(p^k) = p^k − p^(k-1). Para a, b coprimos: φ(a×b) = φ(a)×φ(b) (multiplicativa). General: φ(n) = n × ∏(1 − 1/p) para cada primo p distinto que divide n. Ejemplo: φ(12) = 12 × (1−1/2) × (1−1/3) = 12 × 1/2 × 2/3 = 4. Enteros coprimos con 12: {1, 5, 7, 11}. Usado en: RSA (teorema de Euler: a^φ(n) ≡ 1 mod n), teoría de grupos.

Un número perfecto es igual a la suma de sus divisores propios (divisores excluyendo él mismo). Ejemplos: 6 = 1+2+3. 28 = 1+2+4+7+14. 496. 8128. Solo se conocen 51 números perfectos; todos los conocidos son pares. Primos de Mersenne: n = 2^(p-1) × (2^p - 1) es perfecto cuando (2^p - 1) es primo (primo de Mersenne). Conceptos relacionados: Número abundante: σ(n) > 2n (suma de todos los divisores > 2×número). Número deficiente: σ(n) < 2n. Números amigos: par donde σ(a) = b+a y σ(b) = a+b. Ejemplo: 220 y 284.