Skip to content
Tutorials Center
My learning

Topics

Lesson 22 of 63 ยท Math for Contests

Number Theory Toolkit

A contest toolkit for number theory in Python: gcd and lcm, extended Euclid, sieves, smallest-prime-factor factorization, divisor enumeration and Euler's totient.

Number theory shows up in contests in two forms. Sometimes it is the whole problem: "how many pairs have gcd 1?" or "list all divisors of every number up to a million". More often it is a small ingredient inside a bigger solution, such as reducing a fraction, grouping numbers by prime factors, or counting numbers that share no factor with n. A handful of tools covers almost all of it, and every one is short enough to type from memory.

This lesson collects those tools and tests each one. The ideas behind primes and sieves are explained in depth in Sieve of Eratosthenes and Primality Testing and Number Theory; here we focus on what to keep in your template and when to reach for each piece. For arithmetic with remainders, see Modular Arithmetic.

gcd, lcm and the extended Euclid algorithm

Python ships math.gcd and math.lcm (the latter since 3.9), and both accept any number of arguments in modern versions. They are fast and exact on big integers, so you never need to write Euclid's loop yourself for plain gcd.

Two identities do most of the work. First, gcd(a, b) * lcm(a, b) == a * b. Second, gcd(a, b) == gcd(b, a % b), which is why gcd of a whole array can be folded left to right.

What you do have to write yourself is the extended Euclid algorithm. It returns g, x, y with a*x + b*y == g. This gives you modular inverses when the modulus is not prime (pow(a, -1, m) also does it, but extended Euclid shows you the coefficients), and it solves linear Diophantine equations a*x + b*y == c: a solution exists exactly when g divides c.

Python gcd, lcm and extended Euclid

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A solution to a Diophantine equation is never alone. If (x0, y0) works, so does (x0 + t*b/g, y0 - t*a/g) for every integer t. Contest problems often ask for the smallest non-negative x, which you get by reducing x0 modulo b/g.

The sieve of Eratosthenes

When the statement asks about all primes up to N (typically N up to a few million), a sieve beats testing each number. In Python the trick is to let slicing do the inner loop. A bytearray marks composites, and sieve[i*i::i] = bytes(len(range(i*i, n+1, i))) zeroes a whole stride in C speed.

The sieve costs O(N log log N) time and N bytes. For N = 10^7 that is 10 MB and well under a second in CPython, which is why you should always prefer it to per-number primality tests when the range is dense.

Smallest prime factor and factorization

To factor many numbers, store for each i its smallest prime factor (spf[i]). Then factoring n is a loop: divide by spf[n] until n becomes 1. Each factorization costs O(log n).

For a single large number, trial division up to its square root is enough: at most about 10^6 steps for n up to 10^12, which is acceptable once but not for 10^5 queries. Pick the tool by the question: many numbers below a bound, use the spf sieve; one or two big numbers, use trial division.

flowchart TD
    A["Need prime information"] --> B["Many values below a bound N?"]
    B -->|yes| C["spf sieve, then O(log n) per factorization"]
    B -->|no| D["How big is n?"]
    D -->|"up to about 10^12"| E["Trial division to sqrt(n)"]
    D -->|"larger"| F["Pollard rho or Miller-Rabin (advanced)"]

Choosing a factorization method by the shape of the input.

Python Sieve, spf table and factorization

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Divisors

Once you have the factorization n = p1^e1 * p2^e2 * ..., everything about the divisors follows from the exponents:

  • The number of divisors is (e1 + 1) * (e2 + 1) * ....
  • The sum of divisors is the product of (1 + p + p^2 + ... + p^e) over each prime.
  • Listing them means choosing an exponent for each prime independently.

If you instead need the divisors of every number up to N, do not factor each one. Use a harmonic-style loop: for each d, append d to every multiple of d. The total work is N/1 + N/2 + ... which is about N ln N.

A quick sanity rule that helps with constraints: a number below 10^9 has at most 1,344 divisors, and a number below 10^18 has at most 103,680. Listing divisors of one number is never the bottleneck.

Euler's totient

The totient phi(n) counts integers in 1..n that are coprime to n. From the factorization:

phi(n) = n * product over primes p | n of (1 - 1/p)

In integers: start with result = n and for each prime p of n do result -= result // p. To get phi for all numbers up to N, run a sieve-like pass: begin with phi[i] = i, and for each prime p and each multiple m of p, apply phi[m] -= phi[m] // p.

Totients matter for Euler's theorem (a^phi(m) == 1 mod m when gcd(a, m) == 1), for counting reduced fractions strictly between 0 and 1 with denominator at most N (that is the sum of phi(2..N)), and for the identity sum of phi(d) over d | n == n, which turns "count pairs by gcd" problems into sums.

Python Divisors and totients, checked against brute force

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Pitfalls to remember

  • range(i*i, n+1, i) in the sieve starts at i*i, because smaller multiples were already crossed out by smaller primes. Starting at 2*i is correct but slower.
  • In the totient sieve, phi[p] == p is the primality test only because composites have already been reduced by their smaller prime factors. Do the loop in increasing order.
  • Do not use floating point (n ** 0.5, math.log) for exact decisions near boundaries. Use math.isqrt(n) for an exact integer square root.
  • A sieve with 10^8 entries is too big for most memory limits. If the range is huge but narrow (for example primes between 10^12 and 10^12 + 10^6), use a segmented sieve: sieve primes up to the square root of the upper end, then cross out multiples inside the window.
  • If you factor numbers repeatedly inside a loop, build the spf table once, outside it.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which identity relates gcd and lcm of two positive integers a and b?

    Every prime appears in a and b with exponents e1 and e2. gcd takes the minimum and lcm the maximum, and min + max = e1 + e2, so the product equals a * b.
  2. 2. You must factor 200,000 different numbers, all at most 5,000,000. What is the best approach?

    The spf table costs about N log log N once, and then each factorization takes only O(log n) steps. Trial division would be around 2,000 steps per number.
  3. 3. n = 2^3 * 3^2 * 5. How many positive divisors does n have?

    The divisor count is (3 + 1) * (2 + 1) * (1 + 1) = 24, one independent choice of exponent per prime.
  4. 4. A solution to 21x + 15y = c exists in integers exactly when:

    The left side is always a multiple of gcd(a, b), and extended Euclid shows every multiple of it can be reached.
  5. 5. What is phi(12), the count of numbers in 1..12 coprime to 12?

    12 = 2^2 * 3, so phi = 12 * (1 - 1/2) * (1 - 1/3) = 4. The coprime numbers are 1, 5, 7 and 11.

Summary

  • Use math.gcd and math.lcm; write extended Euclid yourself for inverses and Diophantine equations.
  • Sieve with a bytearray and slice assignment; start crossing out at i*i.
  • Many factorizations: build an spf table once. One big number: trial division to its integer square root.
  • Divisor count and sum come straight from exponents; divisor lists for all numbers use the N ln N multiples loop.
  • phi(n) comes from the prime factors, and sum of phi(d) for d | n equals n.
  • Prefer integer math (isqrt) over floating point for exact decisions.

Next: Probability and Expected Value