Prime Factorization Calculator

Prime factorization (prime decomposition) expresses a positive integer as a product of prime numbers. Every integer > 1 has a unique prime factorization (Fundamental Theorem of Arithmetic). Example: 360 = 2³ × 3² × 5. Steps: find the smallest prime factor, divide, repeat until quotient is 1. Algorithm: trial division by primes up to √n. Efficient for numbers up to ~10^12; larger numbers require advanced algorithms (Pollard's rho, number field sieve). Prime factorization is computationally hard for very large numbers — this hardness underpins RSA cryptography.

Cryptography: RSA and other public-key systems rely on the difficulty of factoring large numbers. Computing GCD/LCM: GCD(a,b) = product of common prime factors with minimum exponents. LCM(a,b) = product of all prime factors with maximum exponents. Fraction simplification: divide numerator and denominator by GCD. Euler's totient function: φ(n) = n × ∏(1 - 1/p) for each distinct prime factor p. Determining perfect squares: n is a perfect square if all prime factor exponents are even. Number of divisors: (e₁+1)(e₂+1)...(eₖ+1) where eᵢ are the exponents.

The Sieve of Eratosthenes efficiently finds all primes up to N. Algorithm: create boolean array [2..N], mark all true. For each unmarked number p starting from 2: mark all multiples of p (p², p²+p, ...) as composite. Remaining unmarked numbers are prime. Time: O(n log log n), Space: O(n). Optimizations: start marking at p² (smaller multiples already marked), only check odd numbers after 2. For N = 10^6: ~78,498 primes. For N = 10^9: needs segmented sieve to reduce memory. Used in competitive programming and number theory research.

Euler's totient φ(n) counts the integers from 1 to n that are coprime (share no common factors) with n. Key properties: φ(1) = 1. For prime p: φ(p) = p − 1. For prime power: φ(p^k) = p^k − p^(k-1). For coprime a, b: φ(a×b) = φ(a)×φ(b) (multiplicative). General: φ(n) = n × ∏(1 − 1/p) for each distinct prime p dividing n. Example: φ(12) = 12 × (1−1/2) × (1−1/3) = 12 × 1/2 × 2/3 = 4. Integers coprime to 12: {1, 5, 7, 11}. Used in: RSA (Euler's theorem: a^φ(n) ≡ 1 mod n), group theory.

A perfect number equals the sum of its proper divisors (divisors excluding itself). Examples: 6 = 1+2+3. 28 = 1+2+4+7+14. 496. 8128. Only 51 perfect numbers are known; all known ones are even. Mersenne primes: n = 2^(p-1) × (2^p - 1) is perfect when (2^p - 1) is prime (Mersenne prime). Related concepts: Abundant number: σ(n) > 2n (sum of all divisors > 2×number). Deficient number: σ(n) < 2n. Amicable numbers: pair where σ(a) = b+a and σ(b) = a+b. Example: 220 and 284.