Primes, the Sieve and GCD
22 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)Prime numbers, divisors and GCD appear in many coding-round problems, from "is this prime" to "reduce this fraction". Each topic has a slow obvious method and a fast standard one. This lesson shows both and says in plain words what each costs.
Is n prime? Stop at the square root
A prime number is an integer greater than 1 whose only divisors are 1 and itself. A number greater than 1 that has another divisor is called composite.
A prime has no divisor except 1 and itself. Testing every number below n takes O(n) steps. Divisors come in pairs, so one of each pair is at most the square root, and O(sqrt n) tests are enough.
def is_prime(n): if n < 2: return False d = 2 while d * d <= n: if n % d == 0: return False d += 1 return True
print([n for n in range(20) if is_prime(n)])Example 1 · Why the square root is enough
import math
n = 36print([d for d in range(1, n + 1) if n % d == 0])print(math.isqrt(n))[1, 2, 3, 4, 6, 9, 12, 18, 36] 6
What this code does
- The divisors of 36 pair up: 1 with 36, 2 with 18, 3 with 12, 4 with 9 and 6 with 6.
- One number of every pair is at most 6, the square root, so testing up to 6 finds a divisor if one exists.
The loop stops when d * d passes n. Number 1 is not prime, and 2 is the only even prime.
The sieve of Eratosthenes
The sieve of Eratosthenes finds every prime up to n by marking the multiples of each prime as composite. What stays unmarked is prime.
To list all primes up to n, do not test each number. Start with all numbers marked prime. For each prime p, mark its multiples as not prime, starting at p * p, because smaller multiples were already marked.
import math
def sieve(limit): is_prime = [True] * (limit + 1) is_prime[0:2] = [False, False] for p in range(2, math.isqrt(limit) + 1): if is_prime[p]: for multiple in range(p * p, limit + 1, p): is_prime[multiple] = False return [n for n, ok in enumerate(is_prime) if ok]
print(sieve(30))Example 2 · Count primes below 100000 with a fast sieve
import math
limit = 100_000flags = bytearray([1]) * (limit + 1)flags[0] = flags[1] = 0for p in range(2, math.isqrt(limit) + 1): if flags[p]: flags[p * p::p] = bytes(len(range(p * p, limit + 1, p)))print(sum(flags))9592
What this code does
- A bytearray with slice assignment marks all multiples of p at once, which is much faster in Python than an inner loop.
- It finds 9592 primes below 100000.
It costs O(n log log n) time and O(n) memory, much faster than testing every number. Only primes up to the square root of the limit need to mark anything.
GCD and LCM from the standard library
GCD is the greatest common divisor of two integers, the largest integer that divides both. Two numbers whose GCD is 1 are called coprime.
The greatest common divisor (GCD) of two numbers is the largest number that divides both. The least common multiple (LCM) is the smallest number both divide. Python has both in math.
import math
print(math.gcd(84, 36))print(math.lcm(4, 6))print(84 // math.gcd(84, 36))Example 3 · GCD of many numbers, fractions and LCM of a range
import math
print(math.gcd(12, 18, 30))g = math.gcd(18, 24)print(f"{18 // g}/{24 // g}")print(math.lcm(*range(1, 11)))6 3/4 2520
What this code does
math.gcdandmath.lcmaccept any number of arguments.- 18 over 24 reduces to 3 over 4, and 2520 is the smallest number divisible by every number from 1 to 10.
GCD of 84 and 36 is 12. LCM of 4 and 6 is 12. Dividing by the GCD reduces a fraction: 84 over 36 becomes 7 over 3. math.lcm needs Python 3.9 or later.
Euclid's algorithm by hand
Interviews often want the GCD written out. The idea: gcd(a, b) is the same as gcd(b, a % b), and when b reaches 0, a is the answer. Each step shrinks the numbers fast.
def gcd(a, b): while b: a, b = b, a % b return a
print(gcd(84, 36))Example 4 · Euclid's steps, one by one
a, b = 48, 18while b: print(a, b) a, b = b, a % bprint("gcd", a)48 18 18 12 12 6 gcd 6
What this code does
- Each line shows the pair before the step: 48 and 18, then 18 and 12, then 12 and 6.
- When b becomes 0 the loop ends and a, which is 6, is the GCD.
Example 5 · Prime factorisation
def factorize(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
print(factorize(360))print(factorize(97)){2: 3, 3: 2, 5: 1}
{97: 1}What this code does
- Divide out each d as many times as it fits. A factor left over at the end is itself a prime.
- 360 is 2 to the 3, times 3 squared, times 5. The cost is O(sqrt n).
It prints 12. The number of steps grows only with the number of digits, so it is O(log min(a, b)). In real code use math.gcd.
Next step
Check your understanding
10 quick questions