Mathematics · Number Theory
Prime Factorization Calculator
Decomposes any positive integer into its unique product of prime factors using trial division.
Calculator
Formula
Every positive integer n greater than 1 can be expressed as a product of prime powers. Here p₁, p₂, …, pₖ are distinct prime numbers in ascending order, and a₁, a₂, …, aₖ are their corresponding positive integer exponents. This representation is unique for every integer, a fact guaranteed by the Fundamental Theorem of Arithmetic.
Source: Hardy, G. H. & Wright, E. M. (2008). An Introduction to the Theory of Numbers (6th ed.), Oxford University Press — Chapter 1, Theorem 2 (Fundamental Theorem of Arithmetic).
How it works
Every integer greater than 1 is either a prime number itself or can be written as a product of primes in exactly one way (ignoring the order of factors). This guarantee, known as the Fundamental Theorem of Arithmetic, makes prime factorization both unique and meaningful. Knowing the prime factors of a number instantly reveals properties like whether it is divisible by 6, what its greatest common divisor with another number is, or how many total divisors it possesses.
This calculator uses trial division, the most straightforward factorization algorithm. Starting from the smallest prime, 2, the algorithm repeatedly divides the input number by the current candidate. If divisible, that candidate is a prime factor, and the quotient replaces the working number. The exponent is tallied by counting how many times each prime divides cleanly. The candidate is then incremented and the process continues until the candidate squared exceeds the remaining value — at which point any remainder greater than 1 must itself be prime. The result is expressed as n = p₁^a₁ × p₂^a₂ × … × pₖ^aₖ, where each pᵢ is a distinct prime in ascending order and aᵢ is its exponent.
Beyond the factorization itself, several related quantities are computed. The number of divisors of n follows the formula (a₁ + 1)(a₂ + 1)…(aₖ + 1) — a direct consequence of the factorization. The smallest prime factor is particularly useful for quickly determining divisibility. These properties are essential in modular arithmetic, cryptographic key generation, and simplifying radical expressions in algebra.
Worked example
Let us factorize n = 360 step by step using trial division.
Step 1 — Divide by 2: 360 ÷ 2 = 180; 180 ÷ 2 = 90; 90 ÷ 2 = 45. 45 is not divisible by 2. So 2 appears with exponent 3.
Step 2 — Divide by 3: 45 ÷ 3 = 15; 15 ÷ 3 = 5. 5 is not divisible by 3. So 3 appears with exponent 2.
Step 3 — Divide by 5: 5 ÷ 5 = 1. So 5 appears with exponent 1.
Result: 360 = 2³ × 3² × 5¹
Number of distinct prime factors: 3 (namely 2, 3, and 5).
Total prime factors with multiplicity: 3 + 2 + 1 = 6.
Number of divisors: (3 + 1)(2 + 1)(1 + 1) = 4 × 3 × 2 = 24. Indeed, 360 has exactly 24 divisors (1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60, 72, 90, 120, 180, 360).
Is 360 prime? No — it has prime factors other than itself.
Limitations & notes
This calculator uses trial division, which is efficient for numbers up to approximately 1,000,000. Beyond that limit, the algorithm may be slow in a browser environment, so the calculator is capped at 1,000,000. For cryptographically large numbers (hundreds of digits), dedicated algorithms such as Pollard's rho, the quadratic sieve, or the general number field sieve are required — these underpin the security of RSA encryption precisely because factoring very large semi-primes is computationally intractable. Additionally, the input must be a positive integer greater than 1; the number 1 is defined to have no prime factors by convention (it is the empty product), and negative integers or non-integers require a separate treatment involving units and algebraic integers.
Frequently asked questions
What is the Fundamental Theorem of Arithmetic and why does it guarantee unique prime factorization?
The Fundamental Theorem of Arithmetic states that every integer greater than 1 is either prime or can be expressed as a finite product of primes in exactly one way, up to the order of the factors. The proof has two parts: existence (by induction — if a number is not prime, its factors are smaller and can themselves be factored) and uniqueness (by Euclid's lemma, which shows that if a prime divides a product it must divide one of the factors). This uniqueness is what makes prime factorization a reliable fingerprint for every integer.
How do I find the GCD and LCM of two numbers using prime factorization?
Once you have the prime factorizations of two numbers, the GCD (Greatest Common Divisor) is found by taking each shared prime to the minimum of its exponents, while the LCM (Least Common Multiple) uses the maximum of its exponents. For example, 360 = 2³ × 3² × 5 and 504 = 2³ × 3² × 7 give GCD = 2³ × 3² = 72 and LCM = 2³ × 3² × 5 × 7 = 2520. Note that GCD(a, b) × LCM(a, b) = a × b always.
Why is 1 not considered a prime number?
If 1 were prime, the Fundamental Theorem of Arithmetic would fail because factorizations would no longer be unique — you could insert any number of factors of 1 into any factorization (e.g., 6 = 2 × 3 = 1 × 2 × 3 = 1 × 1 × 2 × 3, and so on). By excluding 1 from the primes, uniqueness is preserved. Formally, 1 is called a unit in ring theory, a distinct category from primes or composite numbers.
How is prime factorization used in cryptography?
RSA encryption, one of the most widely used public-key cryptosystems, relies on the computational difficulty of factoring the product of two large prime numbers (a semiprime). While multiplying two 1024-bit primes takes milliseconds, factoring their product using the best known algorithms would take longer than the age of the universe on current hardware. This asymmetry between multiplication and factorization creates the secure trap-door function at the heart of RSA, TLS certificates, and digital signatures.
What is the difference between a prime factor and a prime factor with multiplicity?
A distinct prime factor is counted once regardless of how many times it divides the number. For example, 72 = 2³ × 3² has 2 distinct prime factors (2 and 3). With multiplicity, each occurrence is counted separately: 72 has 3 + 2 = 5 total prime factors. The latter count is denoted Ω(n) in number theory (the big omega function), while the count of distinct primes is denoted ω(n) (small omega). Both measures appear frequently in analytic number theory.
Last updated: 2025-01-15 · Formula verified against primary sources.