Prime Factorization Formula – Fundamental Theorem of Arithmetic

The complete prime factorization formula with variable definitions, divisor-count formula, GCD and LCM derivations, and four fully worked examples.

Formula

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

Every integer n > 1 can be uniquely expressed as an ordered product of prime powers. The exponents eᵢ are positive integers, and the primes p₁ < p₂ < … < pₖ are distinct.

Variables

Symbol	Name	Description	Unit
n	Integer to factorize	The positive integer being decomposed into prime factors (n > 1)	—
pᵢ	Prime factor	The i-th distinct prime divisor of n, listed in increasing order	—
eᵢ	Exponent	The number of times prime pᵢ divides n exactly; always ≥ 1	—
k	Number of distinct primes	The count of unique prime factors of n	—
τ(n)	Divisor count	Total number of positive divisors of n: τ(n) = (e₁+1)(e₂+1)⋯(eₖ+1)	—

How to Use

Divide n by 2 as many times as possible. Record each division.
Try odd divisors d = 3, 5, 7, … up to √n, dividing each time d divides the remaining quotient.
If the remaining quotient after the loop is greater than 1, it is itself a prime factor.
Group repeated prime factors using exponents to write the compact exponential form.
Compute τ(n) = (e₁+1)(e₂+1)⋯(eₖ+1) to find the total number of divisors.

Examples

1. Factorize 360

Divide repeatedly by 2, then by 3, then check remaining factors.

Step	Number	÷	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

τ (360) = (3 + 1) (2 + 1) (1 + 1) = 4 \times 3 \times 2 = 24 divisors

ℹ360 has 3 distinct prime factors and 24 total divisors.

2. Factorize 2,310 — a primorial

2,310 = 2 × 3 × 5 × 7 × 11 is the product of the first five primes (called a primorial). Each prime appears exactly once.

Step	Number	÷	Quotient
1	2310	2	1155
2	1155	3	385
3	385	5	77
4	77	7	11
5	11	11	1

2310 = 2 \times 3 \times 5 \times 7 \times 11

τ (2310) = 2^{5} = 32 divisors

ℹWhen all exponents are 1, the divisor count is 2^k where k is the number of prime factors.

3. GCD and LCM from factorizations

Find GCD(360, 756) and LCM(360, 756).

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

756 = 2^{2} \times 3^{3} \times 7

Prime	Exp in 360	Exp in 756	GCD (min)	LCM (max)
2	3	2	2	3
3	2	3	2	3
5	1	0	0	1
7	0	1	0	1

g cd (360, 756) = 2^{2} \times 3^{2} = 4 \times 9 = 36

lcm (360, 756) = 2^{3} \times 3^{3} \times 5 \times 7 = 8 \times 27 \times 5 \times 7 = 7560

ℹVerify: GCD × LCM = 36 × 7560 = 272,160 = 360 × 756. ✓

4. Is 1,000,003 prime? (large number trial division)

We only need to test divisors up to √1,000,003 ≈ 1000.0015. Test primes up to 1000.

After testing all primes ≤ 1000 (there are 168 of them), none divide 1,000,003 evenly.

1, 000, 003 is prime

ℹThe trial division upper bound is √n, not n. For n = 10⁶, only ~168 prime divisors need to be tested — making trial division very efficient for numbers up to 10¹².

Use the Calculator — Interactive calculator for this formula
Read the Notes — Step-by-step explanation with worked examples