Primes and Factorization

Number theory shows up constantly in competitive programming — not because problems explicitly say "this is a number theory problem," but because the properties of primes, divisors, and modular arithmetic are tools you reach for in ad hoc problems, combinatorics, and even graph tasks.

This page covers the foundations: what primes are, how to test for them, how to decompose any number into its prime building blocks, and how to do all of this efficiently.

What Makes a Number Prime?

A prime number is a number greater than 1 that can't be expressed as a product of two smaller positive integers. It has no divisors other than 1 and itself.

The first few: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ...

The key insight for competitive programming isn't the definition — it's this property:

If $n$ has a factor other than 1 and itself, at least one of those factors is $\le \sqrt{n}$.

Why? If $n = a \times b$ and both $a > \sqrt{n}$ and $b > \sqrt{n}$, then $a \times b > n$. Contradiction. So at least one factor must be $\le \sqrt{n}$.

This immediately gives you an efficient primality test.

Primality Testing

The O(sqrt n) Test

To check if $n$ is prime, try dividing by every integer from 2 up to $\sqrt{n}$. If any of them divide evenly, $n$ is composite. If none do, $n$ is prime.

bool isPrime(long long n) {
    if (n < 2) return false;
    for (long long i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

Notice i * i <= n instead of i <= sqrt(n). This avoids floating-point issues. The condition is mathematically equivalent.

For $n = 10^9$, this checks about $\sqrt{10^9} \approx 31623$ divisors. Fast enough for a single number. For checking many numbers, you'll want a sieve (covered below).

A Common Mistake

Beginners sometimes iterate up to $n/2$ thinking "no factor can be bigger than half of $n$." That's true but wasteful. The $\sqrt{n}$ bound is tighter by a factor of $\sqrt{n}$.

Prime Factorization

Every integer $n > 1$ can be written as a product of primes. This is the Fundamental Theorem of Arithmetic.

\[60 = 2^2 \times 3 \times 5$$ $$100 = 2^2 \times 5^2$$ $$17 = 17 \quad \text{(prime — it's its own factorization)}\]

Think of any number as a set of prime factors with multiplicities. The number 60 is the set $\{2, 2, 3, 5\}$. Or written as a map: $\{2 \to 2, \, 3 \to 1, \, 5 \to 1\}$.

This "prime representation" is incredibly useful. As we'll see on the next page, GCD and LCM become simple set operations on this representation.

Finding Prime Factors in O(sqrt n)

The algorithm: try dividing by each potential factor starting from 2. When you find one that divides $n$, divide it out completely (to get the multiplicity), then move on.

vector<pair<int,int>> factorize(int n) {
    vector<pair<int,int>> factors;
    for (int i = 2; (long long)i * i <= n; i++) {
        if (n % i == 0) {
            int count = 0;
            while (n % i == 0) {
                n /= i;
                count++;
            }
            factors.push_back({i, count});
        }
    }
    if (n > 1) {
        factors.push_back({n, 1});  // remaining prime factor
    }
    return factors;
}

The if (n > 1) at the end catches the case where $n$ has a prime factor larger than $\sqrt{n}$. There can be at most one such factor (if there were two, their product would exceed $n$).

Example: factorize 84.

$i$	$n$ before	Divides?	Action	$n$ after
2	84	Yes	Divide twice: 84 → 42 → 21	21
3	21	Yes	Divide once: 21 → 7	7
4	7	No ($4^2 = 16 > 7$)	Stop loop	7

$n = 7 > 1$, so 7 is the remaining prime factor. Result: $84 = 2^2 \times 3 \times 7$.

How Many Distinct Prime Factors?

A number $n$ has at most $\log_2(n)$ distinct prime factors.

Why? The smallest prime is 2. If $n$ has $k$ distinct prime factors, each at least 2, then $n \ge 2^k$. So $k \le \log_2(n)$.

For $n = 10^9$: at most about 30 distinct primes. For $n = 10^{18}$: at most about 60. In practice, numbers rarely have more than a handful of distinct prime factors.

This bound matters for algorithm design. Any loop over the prime factors of $n$ runs in $O(\log n)$ time — essentially free.

The Sieve of Eratosthenes

What if you need to know which numbers are prime for all numbers up to $N$? Running the $O(\sqrt{n})$ test for each number individually would cost $O(N\sqrt{N})$. The Sieve of Eratosthenes does it in $O(N \log \log N)$ — nearly linear.

The Idea

Start with all numbers 2 through $N$ marked as "prime." Then:

Find the smallest unmarked number $p$. It's prime.
Mark all multiples of $p$ (from $p^2$ up to $N$) as composite.
Repeat until $p^2 > N$.

Why start marking from $p^2$? Because smaller multiples like $2p, 3p, \ldots, (p-1)p$ have already been marked by smaller primes.

The Code

vector<bool> sieve(int N) {
    vector<bool> is_prime(N + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; (long long)i * i <= N; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j <= N; j += i) {
                is_prime[j] = false;
            }
        }
    }
    return is_prime;
}

For $N = 10^7$, this runs in well under a second. For $N = 10^8$, it's still feasible with some care (bitwise sieve). Beyond that, you need segmented sieves or other tricks.

Smallest Prime Factor Sieve

A useful variant: instead of just marking composite/prime, store the smallest prime factor (SPF) of each number.

vector<int> spf(N + 1);
iota(spf.begin(), spf.end(), 0);  // spf[i] = i initially
for (int i = 2; (long long)i * i <= N; i++) {
    if (spf[i] == i) {  // i is prime
        for (int j = i * i; j <= N; j += i) {
            if (spf[j] == j) spf[j] = i;
        }
    }
}

Now you can factorize any number $n \le N$ in $O(\log n)$: repeatedly divide by spf[n].

// Factorize n using precomputed SPF table
while (n > 1) {
    int p = spf[n];
    int count = 0;
    while (n % p == 0) { n /= p; count++; }
    // p appears 'count' times
}

This is much faster than trial division when you need to factorize many numbers.

Number of Divisors

A side topic that comes up often: how many divisors does $n$ have?

If $n = p_1^{a_1} \times p_2^{a_2} \times \ldots \times p_k^{a_k}$, then the number of divisors is:

\[d(n) = (a_1 + 1)(a_2 + 1) \cdots (a_k + 1)\]

Why? Each divisor is formed by choosing an exponent for $p_1$ (from 0 to $a_1$), an exponent for $p_2$ (from 0 to $a_2$), and so on. The choices are independent, so you multiply.

Example: $60 = 2^2 \times 3^1 \times 5^1$. Divisors: $(2+1)(1+1)(1+1) = 12$. Indeed: 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60 — twelve divisors.

This formula is also useful for checking whether a number is a perfect square (all exponents must be even, so all $(a_i + 1)$ terms are odd, making the total divisor count odd).

What's Next

Primes and factorization give you the vocabulary. The next page — GCD, LCM, and Modular Arithmetic — shows you how to use that vocabulary: computing GCDs and LCMs via prime representations, modular arithmetic properties, Fermat's Little Theorem for modular inverses, and Euler's Totient Function.

\(i\)	\(n\) before	Divides?	Action	\(n\) after
2	84	Yes	Divide twice: 84 → 42 → 21	21
3	21	Yes	Divide once: 21 → 7	7
4	7	No (\(4^2 = 16 > 7\))	Stop loop	7