Prime Factorization Algorithms — Definition, Formula & Examples

Prime factorization algorithms are systematic methods for decomposing a positive integer into a product of prime numbers. The two most common approaches taught in school are the factor tree method and repeated division (also called the ladder or stacked division method).

A prime factorization algorithm is a deterministic procedure that, given any integer $n > 1$ , produces the unique set of prime factors $p_1, p_2, \ldots, p_k$ and their corresponding exponents $e_1, e_2, \ldots, e_k$ such that $n = p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}$ , as guaranteed by the Fundamental Theorem of Arithmetic.

How It Works

**Factor tree method:** Pick any factor pair of

n

, then split each composite factor into smaller factors, continuing until every branch ends at a prime. **Repeated division method:** Divide

n

by the smallest prime that divides it evenly, then repeat on the quotient until the quotient itself is prime. Both methods always yield the same final answer. You only need to test prime divisors up to

\sqrt{n}

, because if

n

has no prime factor at or below its square root, then

n

is itself prime.

Worked Example

Problem: Find the prime factorization of 360 using repeated division.

Step 1: Divide 360 by the smallest prime, 2.

360 \div 2 = 180

Step 2: Keep dividing by 2 as long as the quotient is even.

180 \div 2 = 90, \quad 90 \div 2 = 45

Step 3: 45 is odd, so move to the next prime, 3.

45 \div 3 = 15, \quad 15 \div 3 = 5

Step 4: 5 is prime, so the process is complete. Collect all the prime divisors used.

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

Answer:

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

Why It Matters

Finding prime factorizations is the key step when computing the GCF or LCM of two numbers, simplifying fractions, and determining whether a number is a perfect square or perfect cube. In computer science and cryptography, the difficulty of factoring very large numbers is the basis for RSA encryption.

Common Mistakes

Mistake: Stopping the division too early by treating a composite quotient (like 9 or 15) as prime.

Correction: Always check whether the current quotient is divisible by small primes (2, 3, 5, 7, …) before declaring it prime. A quotient is prime only when no prime up to its square root divides it.