Sieve of Eratosthenes & Number Theory

Definition

The sieve marks multiples of each prime to list all primes up to n; GCD uses Euclid's algorithm.

Math problems appear often in coding rounds.

Diagram

Flowchart

Example: Primes and GCD

n = 20
p = [True] * (n + 1)
for i in range(2, int(n ** 0.5) + 1):
    if p[i]:
        for j in range(i * i, n + 1, i): p[j] = False
print([i for i in range(2, n + 1) if p[i]])
def gcd(a, b):
    while b: a, b = b, a % b
    return a
print(gcd(48, 18))

Output: [2, 3, 5, 7, 11, 13, 17, 19] 6

Complexity

Sieve O(n log log n) · GCD O(log n)

Key points

• lcm(a,b) = a·b / gcd(a,b)
• Use modulo 10⁹+7 for large counts

Interview questions

More DSA topics