Number Theory Interview Patterns: GCD, Sieve of Eratosthenes, Fast Exponentiation, and Modular Arithmetic (2025)

By /
⏱ 5 min read

When Number Theory Appears in Interviews

Number theory problems appear in interviews at companies like Google, Facebook, and competitive programming contexts. Key topics: GCD/LCM (Euclidean algorithm), prime generation (Sieve of Eratosthenes), modular arithmetic and fast exponentiation, and combinatorics with modular inverses. Recognize them by: “find the number of divisors”, “count primes up to N”, “compute X^Y mod M”, “find all pairs with GCD = K”.

GCD and LCM

Euclidean algorithm: gcd(a, b) = gcd(b, a % b). Base case: gcd(a, 0) = a. O(log(min(a,b))). Why it works: any common divisor of a and b also divides a % b (since a % b = a – k*b). LCM: lcm(a, b) = a * b // gcd(a, b). Compute LCM via GCD to avoid overflow — divide before multiplying: lcm = (a // gcd(a, b)) * b.

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a // gcd(a, b) * b

Applications: find the smallest number divisible by all numbers in a list (LCM of all). Find numbers divisible by both A and B up to N (N // lcm(A, B)). Reduce a fraction: divide numerator and denominator by GCD.

Sieve of Eratosthenes

Generate all primes up to N in O(N log log N). Initialize a boolean array is_prime[0..N] = True. Set is_prime[0] = is_prime[1] = False. For each i from 2 to sqrt(N): if is_prime[i]: mark all multiples of i starting from i*i as False. Remaining True entries are prime.

def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if is_prime[i]:
            for j in range(i*i, n+1, i):
                is_prime[j] = False
    return [i for i, p in enumerate(is_prime) if p]

Segmented sieve for very large N (memory constraint): generate primes up to sqrt(N) with the basic sieve, then sieve segments of size sqrt(N) one at a time. Smallest prime factor sieve: store the smallest prime factor (SPF) for each number. Factorize any number in O(log n) by dividing by SPF repeatedly.

Fast Exponentiation (Binary Exponentiation)

Compute base^exp in O(log exp) via repeated squaring. If exp is even: base^exp = (base^(exp//2))^2. If odd: base^exp = base * base^(exp-1). Always apply modulo at each step to keep numbers small.

def power(base, exp, mod):
    result = 1
    base %= mod
    while exp > 0:
        if exp % 2 == 1:
            result = result * base % mod
        base = base * base % mod
        exp //= 2
    return result

Applications: compute large Fibonacci numbers mod M, count combinations mod prime (use Fermat’s little theorem for modular inverse), cryptography (RSA).

Modular Arithmetic

Key properties: (a + b) % m = ((a % m) + (b % m)) % m. Same for multiplication. For division: modular inverse. If m is prime, modular inverse of a = a^(m-2) % m (Fermat’s little theorem: a^(m-1) ≡ 1 mod m, so a^(m-2) ≡ a^(-1) mod m). Use this for nCr mod prime: precompute factorials and inverse factorials. nCr % MOD = fact[n] * inv_fact[r] % MOD * inv_fact[n-r] % MOD.

Common Interview Problems

Count primes up to N (LC 204): Sieve of Eratosthenes. Ugly numbers (LC 264): only prime factors 2, 3, 5 — use three pointers DP. Pow(x, n) (LC 50): fast exponentiation, handle negative n. GCD of array: fold with gcd function. Find all divisors of N: iterate up to sqrt(N), add both i and N//i if N%i==0. Count numbers in [1, N] divisible by A or B: N//A + N//B – N//lcm(A,B) (inclusion-exclusion).

Asked at: Meta Interview Guide

Asked at: Apple Interview Guide

Asked at: Coinbase Interview Guide

Asked at: LinkedIn Interview Guide

Scroll to Top