GCD, primes and the sieve

Clues: count the primes below n, or find the GCD of two numbers. Worked example: LeetCode 204, Count Primes (Medium): count the primes strictly less than n. Free references: GeeksforGeeks, "Sieve of Eratosthenes" and "Euclidean algorithms (Basic and Extended)".

The idea

The sieve is a roll call. Students 2 to 19 stand up. The first one standing is prime: that's 2, because no smaller number sat it down. It sits down all its multiples: 4, 6, 8 and so on up to 18. Repeat with the next one standing. Whoever never sits down is prime, and you never divide.

Start crossing out at p × p. After 2's turn it's 3's turn, and 6 = 3 × 2 already sat down for 2, so 3 starts at 3 × 3 = 9. Stop once p × p ≥ n: for n = 20, p = 5 gives 25, so stop.

GCD by Euclid. The GCD is the biggest number that divides both. The rule: gcd(a, b) = gcd(b, a mod b), where a mod b is what's left after fitting in as many b's as you can. It's safe because 18 = 12 + 6, so anything that divides 18 and 12 also divides 6.

The walk

Primes below 20: 2, 3, 5, 7, 11, 13, 17, 19, so 8. Quick check from the post: there are 10 primes below 30 (2, 3, 5, 7, 11, 13, 17, 19, 23, 29).

gcd(18, 12), one row per turn of the loop:

a	b	a mod b
18	12	6
12	6	0
6	0	stop: return a

The GCD is 6. gcd(12, 18) works too: the first turn just swaps them.

Pseudocode

Pseudocode · any language

function countPrimes(n):
    if n < 3:  // only 0 and 1 are below n
        return 0
    isPrime = array of n values, all true
    set isPrime[0] and isPrime[1] to false
    p = 2
    while p * p < n:
        if isPrime[p]:
            m = p * p
            while m < n:
                isPrime[m] = false
                m = m + p
        p = p + 1
    return number of true values in isPrime

function gcd(a, b):
    while b != 0:
        remainder = a mod b
        a = b
        b = remainder
    return a

The trap: mark 0 and 1. They start as true; forget the line that sets them to false and they get counted. countPrimes(10) then returns 6 instead of 4 (only 2, 3, 5 and 7 are prime).

Code

class Solution {
    public int countPrimes(int n) {
        if (n < 3) return 0;  // only 0 and 1 are below n
        boolean[] isPrime = new boolean[n];
        java.util.Arrays.fill(isPrime, true);
        isPrime[0] = false;
        isPrime[1] = false;
        long p = 2;
        while (p * p < n) {
            if (isPrime[(int) p]) {
                long m = p * p;
                while (m < n) {
                    isPrime[(int) m] = false;
                    m = m + p;
                }
            }
            p = p + 1;
        }
        int count = 0;
        for (boolean b : isPrime) if (b) count++;
        return count;
    }

    public static int gcd(int a, int b) {
        while (b != 0) {
            int remainder = a % b;
            a = b;
            b = remainder;
        }
        return a;
    }
}

def count_primes(n: int) -> int:
    if n < 3:  # only 0 and 1 are below n
        return 0
    is_prime = [True] * n
    is_prime[0] = False
    is_prime[1] = False
    p = 2
    while p * p < n:
        if is_prime[p]:
            m = p * p
            while m < n:
                is_prime[m] = False
                m = m + p
        p += 1
    return sum(is_prime)

def gcd(a: int, b: int) -> int:
    while b != 0:
        remainder = a % b
        a = b
        b = remainder
    return a

#include <vector>

int countPrimes(int n) {
    if (n < 3) return 0;  // only 0 and 1 are below n
    std::vector<bool> isPrime(n, true);
    isPrime[0] = false;
    isPrime[1] = false;
    long long p = 2;
    while (p * p < n) {
        if (isPrime[p]) {
            long long m = p * p;
            while (m < n) {
                isPrime[m] = false;
                m = m + p;
            }
        }
        p = p + 1;
    }
    int count = 0;
    for (bool b : isPrime) if (b) count++;
    return count;
}

int gcd(int a, int b) {
    while (b != 0) {
        int remainder = a % b;
        a = b;
        b = remainder;
    }
    return a;
}

function countPrimes(n) {
  if (n < 3) return 0;  // only 0 and 1 are below n
  const isPrime = new Uint8Array(n).fill(1);
  isPrime[0] = 0;
  isPrime[1] = 0;
  let p = 2;
  while (p * p < n) {
    if (isPrime[p]) {
      let m = p * p;
      while (m < n) {
        isPrime[m] = 0;
        m = m + p;
      }
    }
    p = p + 1;
  }
  let count = 0;
  for (let i = 0; i < n; i++) count += isPrime[i];
  return count;
}

function gcd(a, b) {
  while (b !== 0) {
    const remainder = a % b;
    a = b;
    b = remainder;
  }
  return a;
}

Complexity

Function	Time	Extra space
`countPrimes`	O(n log log n)	O(n)
`gcd`	O(log(min(a, b)))	O(1)

Each prime p crosses out about n / p numbers, and the sum of n / p over primes up to n grows like n log log n: for n = 1,000,000 that's about 2.1 million crossings in all. In gcd, the numbers at least halve every two turns.

How it was tested

The slide checks run on this code: primes below 20 = 8, primes below 30 = 10, countPrimes(10) = 4 (and 6 if 0 and 1 are left marked true), gcd(18, 12) = 6. On 31 October 2026 both functions in all four languages were run on 3,008 inputs (3,000 random n from 0 to 2,000 with random pairs up to 1,000, the slide examples, the edge cases n = 0, 1, 2 and 3 and gcd(6, 0), and n = 5,000,000 with a pair near 10⁹) and matched trial division and a reference GCD on every one.