Skip to main content
Math for Competitive Programming·Lesson 1 of 5

Number Theory and Primes

Number theory problems appear in nearly every competitive programming contest. Mastery of primes, divisors, and factorisation unlocks a large problem class.

Prime Factorisation

Every integer > 1 has a unique prime factorisation (Fundamental Theorem of Arithmetic):

360 = 2³ × 3² × 5

Trial division: divide by primes up to √n.

def factorise(n):
    factors = {}
    d = 2
    while d * d <= n:
        while n % d == 0:
            factors[d] = factors.get(d, 0) + 1
            n //= d
        d += 1
    if n > 1:
        factors[n] = factors.get(n, 0) + 1
    return factors

factorise(360)   # {2: 3, 3: 2, 5: 1}

O(√n). For n up to 10¹², this is fast enough. For larger n, Pollard's rho algorithm factors in O(n^(1/4)).

Counting Divisors

If n = p₁^a₁ × p₂^a₂ × ... × pₖ^aₖ, then the number of divisors is:

d(n) = (a₁ + 1)(a₂ + 1)...(aₖ + 1)

From factorisation:

def count_divisors(n):
    total = 1
    for exp in factorise(n).values():
        total *= (exp + 1)
    return total

count_divisors(360)   # (3+1)(2+1)(1+1) = 24

Sieve of Eratosthenes

Find all primes up to N in O(N log log N):

def sieve(n):
    is_prime = bytearray([1]) * (n + 1)
    is_prime[0] = is_prime[1] = 0
    for i in range(2, int(n**0.5) + 1):
        if is_prime[i]:
            is_prime[i*i::i] = bytearray(len(is_prime[i*i::i]))
    return [i for i in range(2, n + 1) if is_prime[i]]

Using bytearray and slice assignment makes this significantly faster in Python.

Linear Sieve

The standard sieve marks composites multiple times. The linear sieve marks each composite exactly once — O(N) time. It also computes the smallest prime factor (SPF) of every number, enabling O(log n) factorisation.

def linear_sieve(n):
    spf = list(range(n + 1))   # spf[i] = smallest prime factor of i
    primes = []
    for i in range(2, n + 1):
        if spf[i] == i:        # i is prime
            primes.append(i)
        for p in primes:
            if p > spf[i] or i * p > n:
                break
            spf[i * p] = p
    return primes, spf

primes, spf = linear_sieve(10**6)

def factorise_fast(n, spf):
    factors = []
    while n > 1:
        factors.append(spf[n])
        n //= spf[n]
    return factors

Euler's Totient Function

φ(n) counts the integers from 1 to n that are coprime to n.

φ(n) = n × ∏(1 - 1/p) for all prime p dividing n
def totient(n):
    result = n
    p = 2
    temp = n
    while p * p <= temp:
        if temp % p == 0:
            while temp % p == 0:
                temp //= p
            result -= result // p
        p += 1
    if temp > 1:
        result -= result // temp
    return result

Key property: φ(p) = p - 1 for prime p. This powers Fermat's little theorem.

Multiplicative: if gcd(a, b) = 1, then φ(ab) = φ(a)φ(b). Compute φ for all n ≤ N using a sieve:

def totient_sieve(n):
    phi = list(range(n + 1))
    for i in range(2, n + 1):
        if phi[i] == i:          # i is prime
            for j in range(i, n + 1, i):
                phi[j] -= phi[j] // i
    return phi

Number of Divisors Sieve

Count divisors for all numbers up to N in O(N log N):

def divisor_count_sieve(n):
    d = [0] * (n + 1)
    for i in range(1, n + 1):
        for j in range(i, n + 1, i):
            d[j] += 1
    return d

Sum of Divisors

σ(n) = sum of all divisors of n. Similarly computed via sieve:

def divisor_sum_sieve(n):
    s = [0] * (n + 1)
    for i in range(1, n + 1):
        for j in range(i, n + 1, i):
            s[j] += i
    return s

GCD and LCM at Scale

from math import gcd
from functools import reduce

def lcm(a, b): return a * b // gcd(a, b)

# GCD of a list
gcd_list = reduce(gcd, numbers)
lcm_list = reduce(lcm, numbers)

Key property: gcd(a, b) × lcm(a, b) = a × b.

Common Contest Patterns

Is n a perfect square?

def is_perfect_square(n):
    r = int(n**0.5)
    return r * r == n or (r+1)*(r+1) == n

Count integers in [1, n] divisible by a or b:

def count_div(n, a, b):
    return n//a + n//b - n//lcm(a, b)   # inclusion-exclusion

Smallest n such that n! is divisible by p^k (Legendre's formula):

The exponent of prime p in n! is:

def exp_in_factorial(n, p):
    count = 0
    pk = p
    while pk <= n:
        count += n // pk
        pk *= p
    return count

Key Takeaways

  • Factorise n in O(√n) via trial division; use SPF sieve for O(log n) per query after O(N) preprocessing.
  • d(n) = Π(eᵢ + 1) over prime factorisation exponents.
  • Linear sieve: O(N) sieve that computes SPF for every number up to N.
  • Euler's totient φ(n): count of coprime integers ≤ n. φ(p) = p-1 for prime p.
  • Legendre's formula: exponent of prime p in n! is Σ⌊n/pᵏ⌋.
  • These primitives recur throughout number theory problems — invest time in implementing them cleanly and fast.