GCD/LCM (Euclidean Algorithm) & Sieve of Eratosthenes

Math Algorithm Foundations

Euclidean Algorithm finds Greatest Common Divisor via `gcd(a, b) = gcd(b, a % b)`.

Production Code Example:

import java.util.Arrays;
public class MathAlgos {
    public int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
    public int lcm(int a, int b) { return (a / gcd(a, b)) * b; }
    public boolean[] sieve(int n) {
        boolean[] isPrime = new boolean[n + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        for (int p = 2; p * p <= n; p++) {
            if (isPrime[p]) {
                for (int i = p * p; i <= n; i += p) isPrime[i] = false;
            }
        }
        return isPrime;
    }
}

Key Complexity & Algorithmic Takeaways:

When implementing GCD/LCM (Euclidean Algorithm) & Sieve of Eratosthenes in coding interviews and production applications, keep these core guidelines in mind:

• Time Complexity Analysis: Always evaluate best-case, average-case, and worst-case time complexities ($O(1)$, $O(\log n)$, $O(n)$, $O(n \log n)$, $O(n^2)$).
• Space Complexity & Memory Bounds: Account for auxiliary memory usage, call stack frame recursion overhead, and heap allocations.
• Edge Cases & Validation: Test empty inputs, null pointers, single-element collections, duplicate values, and integer overflow bounds.
• Optimal vs Naive Solutions: Start with a clear brute-force solution, then optimize using techniques like Hashing, Two Pointers, Windowing, or Dynamic Programming.

Summary Takeaway:

Mastering GCD/LCM (Euclidean Algorithm) & Sieve of Eratosthenes provides the foundational problem-solving skills needed to pass technical coding interviews at top tech companies and write ultra-performant software systems.