Prime Factorization Calculator
Find the complete prime factorization of any number — factor tree, exponential form, all divisors, and step-by-step division method.
What is Prime Factorization?
Prime factorization is the process of breaking a number down into a product of prime numbers. For example, 360 = 2 × 2 × 2 × 3 × 3 × 5, written in exponential form as 2³ × 3² × 5. Every whole number greater than 1 can be expressed this way, and — crucially — the factorization is unique (ignoring the order of factors).
Think of prime factors as the "atoms" of arithmetic. Just as every physical substance is made of combinations of atomic elements, every integer is built from combinations of primes. You cannot break a prime down any further using integer multiplication.
The Fundamental Theorem of Arithmetic
The Fundamental Theorem of Arithmetic guarantees two things: (1) every integer greater than 1 can be written as a product of primes, and (2) this representation is unique up to the order of the factors. This uniqueness is what gives prime factorization its power — it means that if two factorizations look different, they must represent different numbers.
The theorem was proved rigorously by Gauss in 1801, though it was known intuitively much earlier. It underpins vast areas of mathematics including number theory, algebra, and cryptography.
Methods: Trial Division vs Sieve of Eratosthenes
Trial division is the most straightforward method: divide n by 2, then by 3, 5, 7, and successive primes until the quotient is 1. You only need to check primes up to √n, because if n has no prime factor ≤ √n, then n itself is prime. Trial division is efficient enough for numbers up to about 10¹².
The Sieve of Eratosthenes pre-generates a list of all primes up to a given limit, which then speeds up trial division for many factorizations. For very large numbers (hundreds of digits), advanced algorithms like Pollard's rho or quadratic sieve are required.
Factor Tree Method — Step-by-Step Example with 360
A factor tree visually decomposes a number into prime factors:
Applications: HCF/LCM and Cryptography
Prime factorization makes finding HCF (Highest Common Factor) and LCM (Lowest Common Multiple) systematic. For HCF, take each prime that appears in both factorizations with the minimum exponent. For LCM, take each prime that appears in either factorization with the maximum exponent.
In cryptography, RSA encryption is built on the fact that multiplying two large primes p and q is fast, but given only their product n = p×q, finding p and q again is computationally infeasible for sufficiently large n (2048-bit numbers use primes of about 600 decimal digits). This asymmetry secures internet banking, email, and most secure communications.