GCD & the Sieve of Eratosthenes

Reducing fractions, syncing repeating schedules, factoring numbers, hashing with primes: two ancient Greek algorithms still do this work in every contest and in a lot of production code.

intermediate⏱ 12 min read

←Builds on

0Recursion & the Call Stackgcd(a, b) = gcd(b, a mod b) is a one-line recursion.1Arrays & Dynamic ArraysThe sieve is a boolean array indexed by the numbers themselves.0Big-O & Growth RatesEuclid's O(log n) and the sieve's O(n log log n) are growth rates worth recognising.

Leads to→

9Fast Exponentiation & Modular ArithmeticWith a prime modulus, Fermat turns fast powers into a way to divide.

1Learn 2Play 3Check 4Practice

Learn

The idea, the mechanics and the cost.

01Euclid's algorithm

The greatest common divisor gcd(a, b) is the largest number dividing both. Trying every candidate is slow. Euclid noticed that any common divisor of a and b also divides a mod b, because a mod b = a − q·b. So

gcd(a, b) = gcd(b, a mod b), and gcd(a, 0) = a.

For 84 and 60: (84, 60) → (60, 24) → (24, 12) → (12, 0), so the answer is 12 after three divisions. In code it is one line: while (b) { t = a % b; a = b; b = t; }.

Once you have gcd, the least common multiple follows: lcm(a, b) = a / gcd(a, b) * b. Divide first, so the intermediate value does not overflow.

02Why Euclid is so fast

After two steps the larger number at least halves. If b ≤ a/2, then a mod b < b ≤ a/2. If b > a/2, then a mod b = a − b < a/2. Either way the pair shrinks fast, so Euclid takes O(log min(a, b)) steps: about 90 divisions even for 64-bit numbers.

Primality has a similar shortcut. To test whether n is prime you only need to try divisors up to √n, because divisors come in pairs d · (n/d), and one of the pair is always ≤ √n. That gives an O(√n) test, fine for one number up to about 10^12.

But if you need all primes up to n, testing each number separately costs O(n√n). The sieve does much better.

03The Sieve of Eratosthenes

Write 2..n and mark them all "maybe prime". Walk p upward. If p is still unmarked, it is prime, because no smaller prime divides it. Then cross out its multiples. Two details make it fast:

start crossing at p²: smaller multiples like 2p and 3p were already crossed by 2 and 3
stop when p² > n: every composite ≤ n has a prime factor ≤ √n, so everything left is prime

for p in 2..: if p*p > n break; if is[p]: for m = p*p; m <= n; m += p: is[m] = false

The total work is n/2 + n/3 + n/5 + … over primes, which is O(n log log n): practically linear. A sieve up to 10^7 runs in well under a second and needs one byte (or one bit) per number.

Each composite is coloured by the first prime that crossed it out. Only 2, 3 and 5 are needed for n = 40, since 7² = 49 > 40.

04Beyond the basic sieve

A small upgrade makes the sieve far more useful. Instead of a boolean, store spf[m], the smallest prime factor, the first time m is crossed out. Then you can factor any m ≤ n in O(log m): divide by spf[m] repeatedly.

Typical uses:

counting divisors of many numbers (factor, then multiply exponents + 1)
checking coprimality: gcd(a, b) == 1
fractions in lowest terms: divide both parts by their gcd

Pitfalls: 1 is neither prime nor composite, so mark it explicitly. Allocate n + 1 entries. When n is large, compute p * p in 64-bit to avoid overflow.

Cost at a glance

gcd (Euclid)O(log min(a,b))

Primality test by trial divisionO(√n)

Sieve: all primes up to nO(n log log n)

Factor m with an spf sieveO(log m)

Remember

gcd(a, b) = gcd(b, a mod b) until b is 0; it needs only O(log) steps, and lcm = a / gcd · b.
Divisors come in pairs around √n, so primality checks and sieving can stop at √n.
The sieve crosses multiples from p² upward and finds all primes up to n in O(n log log n).

Play

Step through the algorithm, then try it on your own input.

👀 What to watch: First watch (a, b) shrink to (gcd, 0). Then in the sieve, notice that each new prime starts crossing at p², and that the run stops long before n.

Interactive visualizerfocus here, then space ← →

Euclid's algorithm

a	b	a mod b
84	60	·

Sieve of Eratosthenes, 2..60

primejust crossed outcomposite (crossed out)not decided yetcurrent p

gcd(84, 60): any common divisor of a and b also divides a mod b, so we may replace (a, b) by (b, a mod b) without changing the answer.

Pseudocode

 1 gcd(a, b): while b != 0: 2   (a, b) = (b, a mod b) 3   return a 4 is_prime[2..n] = true 5 for p = 2; p * p <= n; p++: 6   if is_prime[p]:                 // p is prime 7     for m = p*p; m <= n; m += p: is_prime[m] = false 8 every number still marked true is prime

1 / 1

Check

Three questions. Pick an answer to see why.

Euclid on (48, 18): which pair comes right after (48, 18)?

Sieving up to n = 100, what is the last p whose multiples we cross out?

Why does the sieve start crossing the multiples of p at p² instead of 2p?

Practice

Real problems to lock it in, easiest first.

LeetCodeFind Greatest Common Divisor of Array beginner↗LeetCodeCount Primes intermediate↗CSESCounting Divisors intermediate↗CSESCommon Divisors advanced↗