Prime Factorization Calculator

Last updated: 2026-05-19

Definition

Every integer greater than 1 can be written as a product of prime numbers. This representation is called the prime factorization. For example:

$360 = 2^3 \cdot 3^2 \cdot 5$

The primes 2, 3, and 5 are the "atoms" of 360 — they cannot be divided further. The exponents (3, 2, and 1) record how many times each prime appears.

The Fundamental Theorem of Arithmetic

The Fundamental Theorem of Arithmetic guarantees two things:

1. Existence: Every integer greater than 1 has at least one prime factorization.
2. Uniqueness: Every integer greater than 1 has exactly one prime factorization (up to the order of factors).

This theorem is the cornerstone of number theory. Without it, arithmetic concepts like GCD, LCM, and divisibility would be far more complicated.

Why is 1 excluded? If 1 were prime, factorizations would no longer be unique — an extra factor of 1 could always be inserted. Excluding 1 from the primes preserves uniqueness.

How Trial Division Works

The most straightforward way to factor $n$ is trial division: test every integer from 2 up to $\sqrt{n}$ as a potential factor.

Step-by-step for n = 360:

1. Is 360 divisible by 2? Yes: $360 = 2 \times 180$. Keep dividing: $180 = 2 \times 90$, $90 = 2 \times 45$. Now 45 is odd. Factor: 2³.
2. Is 45 divisible by 3? Yes: $45 = 3 \times 15$, $15 = 3 \times 5$. Now 5 is not divisible by 3. Factor: 3².
3. Is 5 divisible by 5? Yes: $5 = 5 \times 1$. Factor: 5¹.
4. Nothing remains. Result: $360 = 2^3 \cdot 3^2 \cdot 5$.

Why only up to $\sqrt{n}$? If $n$ has a factor $p > \sqrt{n}$, then $n/p < \sqrt{n}$, meaning a smaller factor must already exist. When no factor $\leq \sqrt{n}$ is found, $n$ itself must be prime.

Factor Trees

A factor tree is a visual method for finding prime factors: a number is repeatedly split into any two factors until every branch ends in a prime.

        360
       /    \
      4      90
     / \    /  \
    2   2  9    10
          / \  / \
         3   3 2  5

The leaves give the prime factorization: 2, 2, 2, 3, 3, 5 → 2³ · 3² · 5.

Factor trees always reach the same result regardless of the order in which the splits are made — a direct consequence of uniqueness.

Counting Divisors

A direct application of prime factorization is counting divisors. If:

$n = p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}$

then the total number of positive divisors is:

$\tau(n) = (e_1 + 1)(e_2 + 1) \cdots (e_k + 1)$

Why? Each divisor of $n$ is formed by independently selecting an exponent for each prime: any value from 0 to $e_i$ for prime $p_i$. That gives $(e_i + 1)$ choices per prime, and the choices multiply.

Example — divisors of 360:

$\tau(360) = (3+1)(2+1)(1+1) = 4 \cdot 3 \cdot 2 = 24$

So 360 has exactly 24 positive divisors.

GCD and LCM via Prime Factorization

Given the factorizations of two numbers, their GCD and LCM follow directly:

• GCD: take the minimum exponent for each prime.
• LCM: take the maximum exponent for each prime.

Example: GCD and LCM of 360 and 504

$360 = 2^3 \cdot 3^2 \cdot 5, \qquad 504 = 2^3 \cdot 3^2 \cdot 7$

Prime	360	504	min (GCD)	max (LCM)
2	3	3	3	3
3	2	2	2	2
5	1	0	0	1
7	0	1	0	1

$\gcd(360, 504) = 2^3 \cdot 3^2 = 72, \qquad \text{lcm}(360, 504) = 2^3 \cdot 3^2 \cdot 5 \cdot 7 = 2520$

Simplifying Fractions

To reduce $\dfrac{a}{b}$ to lowest terms, divide numerator and denominator by $\gcd(a, b)$.

$\frac{360}{504} = \frac{360 \div 72}{504 \div 72} = \frac{5}{7}$

Applications Beyond Arithmetic

Field	How prime factorization helps
Cryptography	RSA security rests on the difficulty of factoring the product of two large primes
Hash functions	Choosing hash-table sizes as primes reduces collisions
Coding theory	Generator polynomials in error-correcting codes factor over finite fields
Music theory	Just intonation intervals are ratios of small prime powers (2, 3, 5)

Special Cases

• n = 2 (smallest prime): Factorization is 2 itself; exactly 2 divisors (1 and 2).
• n is prime: Factorization is just $n$ itself; it has exactly 2 divisors (1 and $n$).
• Perfect powers: Numbers like 1024 = 2¹⁰ have only one distinct prime factor; their divisor count is $e + 1 = 11$.
• Highly composite numbers: Numbers with unusually many divisors (e.g., 360, 720, 1260) have small primes with large exponents.

Quick Reference

Concept	Formula
Factorization	$n = p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}$
Distinct prime count	$\omega(n) = k$
Total divisor count	$\tau(n) = \prod (e_i + 1)$
GCD of two numbers	product of primes with minimum exponents
LCM of two numbers	product of primes with maximum exponents
GCD × LCM identity	$\gcd(a,b) \times \text{lcm}(a,b) = a \times b$

Frequently Asked Questions (FAQ)

What is prime factorization?

Prime factorization is the process of expressing a positive integer as a product of prime numbers. For example, 360 = 2³ · 3² · 5. Every integer greater than 1 can be written this way, and the Fundamental Theorem of Arithmetic guarantees the representation is unique (up to the order of factors).

Is every number's prime factorization unique?

Yes. The Fundamental Theorem of Arithmetic states that every integer greater than 1 has exactly one prime factorization (ignoring the order of factors). This uniqueness is what makes prime factorization so powerful in number theory — it is the "atomic decomposition" of integers.

How do I count all divisors from the prime factorization?

If n = p₁^e₁ · p₂^e₂ · … · pₖ^eₖ, then the total number of positive divisors is τ(n) = (e₁+1)(e₂+1)…(eₖ+1). For 360 = 2³ · 3² · 5¹, τ(360) = 4 · 3 · 2 = 24, so 360 has 24 divisors in total.

What is the largest number this calculator can factor?

This calculator supports integers up to 1,000,000,000,000 (10¹², one trillion). It uses trial division up to √n, which requires at most about one million iterations — fast enough to run in the browser. If you need to factor larger numbers, specialized algorithms such as Pollard's rho or quadratic sieve are used.