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

By /

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).

{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “What is the time complexity of the Euclidean GCD algorithm and why?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “The Euclidean algorithm runs in O(log(min(a, b))) time. At each step, a is replaced by b and b is replaced by a % b. The key insight: after two steps, the value of a decreases by at least half. If b <= a/2: then a % b < b a/2: then a % b = a – b < a – a/2 = a/2 (also halved). So every two iterations, the larger value halves — giving O(log) steps. The number of steps is bounded by 2 * log_phi(max(a,b)) where phi is the golden ratio (Fibonacci numbers are the worst case for the Euclidean algorithm). In practice, it is much faster than the worst case."
}
},
{
"@type": "Question",
"name": "How does the Sieve of Eratosthenes achieve O(N log log N) complexity?",
"acceptedAnswer": {
"@type": "Answer",
"text": "The total work done by the sieve is the sum over all primes p 1: N is a prime factor (the remaining large prime). Time: O(sqrt(N)). For factorizing many numbers efficiently: precompute the Smallest Prime Factor (SPF) sieve. SPF[i] = smallest prime that divides i. Initialize SPF[i] = i for all i. For each prime p in the sieve: for multiples m of p where SPF[m] == m: set SPF[m] = p. Then to factorize N: while N > 1: factor = SPF[N]; divide N by factor repeatedly. This gives all prime factors in O(log N) per number after O(N log log N) preprocessing.”
}
},
{
“@type”: “Question”,
“name”: “How do you use inclusion-exclusion for counting divisibility problems?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Count numbers in [1, N] divisible by A or B: |A u222a B| = |A| + |B| – |A u2229 B| = N//A + N//B – N//lcm(A,B). For three divisors A, B, C: |A u222a B u222a C| = |A| + |B| + |C| – |Au2229B| – |Au2229C| – |Bu2229C| + |Au2229Bu2229C|. Each intersection uses LCM of the corresponding set. For K divisors: iterate over all 2^K subsets, compute LCM of the subset, add or subtract based on subset size parity. Classic problem: count integers from 1 to N not divisible by any prime in a given set (Euler’s totient function). The formula: count = N * product of (1 – 1/p) for each prime p in the set. Scale to integer arithmetic by computing the inclusion-exclusion sum directly.”
}
}
]
}

Asked at: Meta Interview Guide

Asked at: Apple Interview Guide

Asked at: Coinbase Interview Guide

Asked at: LinkedIn Interview Guide

Scroll to Top