Math Overview: GCD, Sieve Methods, and Number Theory

Why Mathematics is Core to Algorithmic Design

Math problems in system optimization don't follow the structured patterns typical of standard data structures. Instead, they require mathematics intuition and the ability to translate formal logic into efficient, scalable code. They distinguish standard CRUD code from systems that truly understand the mechanics of scaling and transformation.

Core math categories on platforms like LeetCode include:

Euclidean Algorithm: The Heart of GCD

The Greatest Common Divisor (GCD) is the largest positive integer that divides each of two or more integers without a remainder.

• Logic: gcd(a, b) = gcd(b, a % b).
• Why? If $d$ divides $a$ and $b$, then $a = q \cdot b + r$ implies $d$ must also divide $r = a - q \cdot b$. Therefore, any common divisor of $(a, b)$ is also a common divisor of $(b, r)$.

Java Implementation

// Iterative (Recommended to avoid StackOverflow)
public int gcd(int a, int b) {
    while (b != 0) {
        int t = b;
        b = a % b;
        a = t;
    }
    return a;
}

// Least Common Multiple (LCM)
public long lcm(long a, long b) {
    if (a == 0 || b == 0) return 0;
    // Divide before multiply to prevent overflow
    return Math.abs(a) / gcd((int)a, (int)b) * Math.abs(b);
}

Prime Sieve: From Brute Force to $O(N)$ Linear Sieve

A prime number is an integer greater than 1 that has no positive divisors other than 1 and itself.

Sieve of Eratosthenes

The most common way to generate all primes up to $N$.

1. Start with a boolean array isPrime for $[2, N]$.
2. For each number $p$, if it's prime, mark all its multiples $2p, 3p, ...$ as not prime.

public List<Integer> sieve(int n) {
    boolean[] notPrime = new boolean[n + 1];
    List<Integer> primes = new ArrayList<>();
    for (int i = 2; i <= n; i++) {
        if (!notPrime[i]) {
            primes.add(i);
            // Optimization: start marking from i*i
            for (long j = (long)i * i; j <= n; j += i) {
                notPrime[(int)j] = true;
            }
        }
    }
    return primes;
}

Complexity: $O(N \log \log N)$. This is almost linear and sufficient for most high-performance scenarios.

Linear Sieve (Euler's Sieve) - $O(N)$

Ensures every composite number is marked exactly once by its smallest prime factor.

public int[] linearSieve(int n) {
    boolean[] notPrime = new boolean[n + 1];
    int[] primes = new int[n];
    int count = 0;
    for (int i = 2; i <= n; i++) {
        if (!notPrime[i]) primes[count++] = i;
        for (int j = 0; j < count && i * primes[j] <= n; j++) {
            notPrime[i * primes[j]] = true;
            if (i % primes[j] == 0) break; // Found the smallest factor
        }
    }
    return Arrays.copyOf(primes, count);
}

Fast Exponentiation (Binary Exponentiation)

Calculating $x^n$ in $O(N)$ is too slow for large $n$ (like $10^9$). Binary exponentiation reduces this to $O(\log N)$.

Logic: Decompose $n$ into powers of 2. $x^{13} = x^{1101_2} = x^8 \cdot x^4 \cdot x^1$.

public double myPow(double x, int n) {
    long k = n;
    if (k < 0) { x = 1 / x; k = -k; }
    
    double res = 1.0;
    while (k > 0) {
        if ((k & 1) == 1) res *= x; // If bit is 1, multiply into result
        x *= x;                    // Square the base
        k >>= 1;                   // Move to next bit
    }
    return res;
}

Pattern-Based Numerical Problems

Happy Number (LeetCode 202) - Floyd's Cycle Finding

A sequence will either end in 1 or enter a cycle. We can use a slow and fast pointer to detect the cycle.

public boolean isHappy(int n) {
    int slow = n, fast = sumSquares(n);
    while (fast != 1 && slow != fast) {
        slow = sumSquares(slow);
        fast = sumSquares(sumSquares(fast));
    }
    return fast == 1;
}

private int sumSquares(int n) {
    int sum = 0;
    while (n > 0) {
        int d = n % 10;
        sum += d * d;
        n /= 10;
    }
    return sum;
}

Engineering Cheat Sheet: Math Logic