Prime Factorization Calculator
Decompose any positive integer into its unique product of prime numbers — the fundamental "atomic" representation that underlies divisibility, fractions, modular arithmetic, and cryptography. The result is returned as a space-separated multiplication expression.
Last updated: May 2026
Compare with similar
About this calculator
Every integer greater than 1 has a unique prime factorisation: a multiset of primes whose product equals the number. This is the Fundamental Theorem of Arithmetic, proven (informally) in Euclid's Elements around 300 BC and rigorously by Gauss in 1801. The calculator uses trial division: start with divisor d = 2, divide n by d as many times as possible (collecting each occurrence), then increment d and repeat until n becomes 1. This naive method is O(√n) in the worst case — for n up to ~10¹⁴ it runs in milliseconds, but for cryptographic-scale integers (hundreds of digits) you need vastly better algorithms (Pollard rho, quadratic sieve, general number field sieve). Variables: n is the positive integer to factor; should be ≥ 2 to produce meaningful output (1 has the empty factorisation by convention, and 0 has no factorisation at all). Edge cases: for n = 1 the calculator returns an empty string (no primes); for prime n it returns just n; for prime powers it lists the prime repeatedly (e.g., 8 → "2 x 2 x 2"); for composite numbers it lists every prime factor counted with multiplicity (e.g., 360 → "2 x 2 x 2 x 3 x 3 x 5"). Negative integers, zero, and non-integers are outside the standard definition. The hardness of factoring large semiprimes (products of two large primes) is what makes RSA encryption secure — the same trial-division algorithm shown here in principle works on any input, but for a 2048-bit RSA modulus would take longer than the age of the universe.
How to use
Example 1 — Standard composite. Factor 360. Enter 360. Trace: 360 / 2 = 180, 180 / 2 = 90, 90 / 2 = 45, 45 / 3 = 15, 15 / 3 = 5, 5 / 5 = 1. Result: "2 x 2 x 2 x 3 x 3 x 5". ✓ Verify: 2³ × 3² × 5 = 8 × 9 × 5 = 360. In exponent form this is 2³ · 3² · 5¹. Example 2 — Prime input. Enter 97. Trial division: 97 is not divisible by 2, 3, 5, or 7 (and we only need to check up to √97 ≈ 9.85). Result: "97". ✓ This means 97 is prime — its only prime factorisation is itself. The calculator confirms primality implicitly: if the only factor returned is the input, the number is prime. (For a dedicated yes/no primality check, use the prime-number-checker calculator.)
Frequently asked questions
Why is prime factorisation important in mathematics?
Because of the Fundamental Theorem of Arithmetic: every integer greater than 1 has exactly one prime factorisation, up to the order of the factors. This uniqueness makes primes the "atoms" of multiplicative number theory — they let you reduce any number-theoretic question to its prime constituents. Divisibility, GCD, LCM, modular inverses, and fraction simplification all become trivial once you have prime factorisations. Prime factorisation also underlies modern cryptography: RSA, DSA, and elliptic-curve schemes derive their security from the assumption that factoring large numbers is computationally intractable. Even questions in pure mathematics like the Riemann hypothesis are ultimately about how primes are distributed among the integers.
How is prime factorisation related to GCF and LCM?
If you know the prime factorisations of a and b, the GCF is just the product of the common primes raised to the minimum exponent, and the LCM is the product of all primes that appear in either, each raised to the maximum exponent. For example, 60 = 2² · 3 · 5 and 84 = 2² · 3 · 7: GCF = 2² · 3 = 12 (min of each prime), LCM = 2² · 3 · 5 · 7 = 420 (max of each prime). This is the "textbook" approach and makes the relationship between GCF, LCM, and the inputs visually clear. In practice, the Euclidean algorithm computes GCD without ever factoring the inputs, which is much faster for large numbers — but for understanding, factorisation gives the deepest intuition.
How can a number be both prime and a factor in a prime factorisation?
A prime number's factorisation is just itself: 7 = 7, 13 = 13, 97 = 97. By definition a prime has exactly two positive divisors (1 and itself), so the only product of primes that equals it is the trivial one with one factor. When this calculator returns a single number as the factorisation, that number is prime — the calculator implicitly verifies primality. A common related question is "is 1 prime?" The answer is no: 1 has only one divisor (itself), and including 1 as a prime would break the uniqueness of factorisations (2 · 3 = 2 · 3 · 1 = 2 · 3 · 1 · 1 ...). The definition specifically excludes 1 to preserve the Fundamental Theorem of Arithmetic.
What are the most common mistakes people make with prime factorisation?
The first is listing composite factors instead of primes: writing 12 = 4 · 3 is correct multiplication but not the prime factorisation (because 4 is not prime); the correct form is 12 = 2² · 3 or "2 x 2 x 3". The second is forgetting to include all repetitions: 8 = 2³, not just "8 has 2 as a factor". The third is treating 1 as a prime and listing it in factorisations, which makes the representation non-unique. The fourth is trying to factor 0 (which has no factorisation) or negative numbers (which need a sign and then factor the absolute value). The fifth is using trial division on very large numbers — for n above ~10¹⁵ trial division becomes painfully slow; for cryptographic-scale numbers it is hopeless, and you need specialised algorithms (Pollard rho, ECM, quadratic sieve).
When should I not use this calculator?
Skip it for very large inputs (more than about 10¹² or 13 digits) — trial division becomes slow, and for numbers beyond 10¹⁵ it is unusable; use specialised factorisation software (PARI/GP, SageMath, Mathematica) or factoring services that implement Pollard rho and quadratic sieve. Do not use it for negative numbers, zero, or one — none have a meaningful prime factorisation in the standard sense (negatives need a separate sign; 0 is divisible by everything; 1 is the empty product). It is the wrong tool when you only need to test primality (is n prime, yes or no?) — use a dedicated prime-number-checker which uses faster tests (Miller-Rabin) than full factorisation. Avoid it for polynomial factorisation, ring-of-integers factorisation in number fields, or factorisation in Gaussian integers — those need their own algorithms and tools. Finally, do not use it for cryptographic key analysis; the algorithm is correct but the implementation cannot handle the integer sizes involved.