How Prime Factorization Works

Prime factorization breaks any integer greater than 1 into a unique product of prime numbers. This page explains the trial division method, factor trees, and how factorization is used to compute GCD, LCM, and is foundational to modern cryptography.

The Fundamental Theorem of Arithmetic

Every integer greater than 1 is either a prime number itself, or can be expressed as a unique product of prime numbers. This uniqueness (up to ordering) is guaranteed by the Fundamental Theorem of Arithmetic.

n = p_{1}^{e_{1}} \times p_{2}^{e_{2}} \times \dots \times p_{k}^{e_{k}}, p_{1} < p_{2} < \dots < p_{k}

ℹThe factorization is unique. For example, 12 = 2² × 3 is the only way to express 12 as a product of primes — there is no other combination.

Trial Division Method

Trial division is the simplest factorization algorithm. Divide the number by increasing integers starting from 2, collecting each successful divisor as a prime factor.

Set d = 2 (the smallest prime).
While d² ≤ n: if d divides n, record d as a factor and replace n with n ÷ d. Repeat until d no longer divides n, then increment d.
If n > 1 after the loop, n itself is a prime factor.

Worked Example: Factorize 360

Step	Number	Divisor	Quotient
1	360	2	180
2	180	2	90
3	90	2	45
4	45	3	15
5	15	3	5
6	5	5	1

360 = 2^{3} \times 3^{2} \times 5

Worked Example: Factorize 1001

1001 looks large but factors quickly. We test divisors up to √1001 ≈ 31.6.

Step	Number	Divisor	Quotient
1	1001	7	143
2	143	11	13
3	13	13	1

1001 = 7 \times 11 \times 13

Counting Divisors

Given the prime factorization n = p₁^e₁ × p₂^e₂ × … × pₖ^eₖ, the total number of positive divisors is:

τ (n) = (e_{1} + 1) (e_{2} + 1) \dots (e_{k} + 1)

For 360 = 2³ × 3² × 5¹: τ(360) = (3+1)(2+1)(1+1) = 4 × 3 × 2 = 24 divisors.

GCD and LCM from Prime Factorization

For two numbers a and b with known prime factorizations:

GCD(a, b): for each prime, take the smaller (minimum) exponent.
LCM(a, b): for each prime, take the larger (maximum) exponent.

Example: a = 360 = 2³ × 3² × 5, b = 756 = 2² × 3³ × 7

g cd (360, 756) = 2^{m i n (3, 2)} \times 3^{m i n (2, 3)} = 2^{2} \times 3^{2} = 36

lcm (360, 756) = 2^{m a x (3, 2)} \times 3^{m a x (2, 3)} \times 5^{1} \times 7^{1} = 2^{3} \times 3^{3} \times 5 \times 7 = 7560

Why Does This Matter? Cryptography

RSA encryption multiplies two large prime numbers p and q to produce n = p × q. Multiplying them takes microseconds. Reversing the process — recovering p and q from n — takes classical computers an astronomical amount of time when p and q are hundreds of digits long. This one-way difficulty is the mathematical foundation of public-key cryptography.

⚠No efficient classical algorithm for general integer factorization is known. The best known method (General Number Field Sieve) still runs in sub-exponential but super-polynomial time. Shor's quantum algorithm could factor in polynomial time, but practical quantum computers of sufficient size do not yet exist.

Prime Factorization Calculator — Factorize any integer up to 10¹² with step-by-step output
Prime Factorization Formula — Formula reference, divisor counting, GCD, and LCM

Frequently Asked Questions

Is the prime factorization of every number unique?

Yes. The Fundamental Theorem of Arithmetic guarantees that every integer greater than 1 has exactly one prime factorization, regardless of the order in which you find the factors.

What is the prime factorization of a prime number?

A prime number p is its own factorization: p = p¹. It has no divisors other than 1 and itself, so there are no smaller prime factors to extract.

How does trial division work for very large numbers?

Trial division tests each candidate divisor d from 2 up to √n. If no divisor is found, the number is prime. The key insight is that if n has a factor larger than √n, it must have a corresponding factor smaller than √n — so checking up to √n is sufficient.

What is a factor tree?

A factor tree is a visual diagram that starts with a number at the top and branches into two factors at each step, continuing until all branches end in prime numbers. It produces the same result as trial division but is easier to draw by hand for small numbers.

What makes a number a perfect square based on its factorization?

A number is a perfect square if and only if every prime factor has an even exponent in its factorization. For example, 36 = 2² × 3² is a perfect square (both exponents are even), while 72 = 2³ × 3² is not (the exponent of 2 is odd).