Math and number theory (GCD, sieve, modular)

How does Math and number theory (GCD, sieve, modular) work?

Euclid's rule replaces a pair of numbers with a smaller pair. The GCD of a and b equals that of b and a modulo b.

It stops when the second number reaches zero. The other number is then the answer.

The least common multiple follows from the GCD. It is a times b divided by their GCD.

A sieve marks the multiples of each prime it meets. Whatever stays unmarked is prime.

Modular arithmetic keeps the numbers small. Take the remainder after every step, not only at the end.

Division has no simple modular form. It needs a modular inverse instead.

1. gcd(48, 18)48 modulo 18 leaves 12.
2. gcd(18, 12)18 modulo 12 leaves 6.
3. gcd(12, 6)12 modulo 6 leaves nothing.
4. gcd(6, 0) = 6The second number hit zero. The answer is 6.
5. lcm = 48 times 18 over 6That gives 144, without listing a single multiple.

function gcd(a, b) {
    while (b !== 0) {
        [a, b] = [b, a % b];
    }
    return a;
}
function lcm(a, b) {
    return (a / gcd(a, b)) * b;
}

A worked example of Math and number theory (GCD, sieve, modular)

Count the primes below n

Count the prime numbers strictly below n.

Testing each number on its own is far too slow once n is large.

Mark every multiple of each prime as composite.

Start marking at the prime squared. Everything smaller already carries a smaller factor.

function countPrimes(n) {
    if (n < 3) return 0;

    const composite = new Array(n).fill(false);
    let count = 0;

    for (let p = 2; p < n; p++) {
        if (composite[p]) continue;
        count++;

        // start at p * p: everything smaller already has a smaller factor
        for (let multiple = p * p; multiple < n; multiple += p) {
            composite[multiple] = true;
        }
    }

    return count;
}

When should you use Math and number theory (GCD, sieve, modular)?

These phrases in a problem statement point here:

• •reduce a fraction to lowest terms
• •list all primes up to n
• •answer modulo 1e9+7
• •when do two repeating intervals line up again (LCM)

What is Math and number theory (GCD, sieve, modular) confused with?

• Bit manipulation: Both work on the number itself. That page is about the individual bits.
• Hash set / map: A set of primes still has to be built somehow. A sieve is how you build it.
• Dynamic programming (1-D): A formula answers at once where DP fills a table. Look for a closed form first.
• Prefix sums: Prefix sums answer over values that were stored. Here the answer comes from the numbers themselves.

Common mistakes with Math and number theory (GCD, sieve, modular)

• Taking the remainder only at the end

  The value overflows long before you get there. Reduce it after every multiplication.

• Getting a negative remainder

  In JavaScript minus one modulo five is minus one. Add the modulus and take the remainder again.

• Starting the sieve's inner loop at twice the prime

  Everything below the prime squared already has a smaller factor. Starting there wastes most of the work.

• Testing divisors past the square root

  A factor above the root always pairs with one below it. Stop at the root.

Which interview problems use Math and number theory (GCD, sieve, modular)?

• Greatest common divisor of strings: The answer's length is the GCD of the two lengths.
• Count primes: A sieve rather than a test per number.
• Ugly number II: Three pointers over the multiples of 2, 3 and 5.
• Power of three: Repeated division, or a single divisibility test.
• Fraction to recurring decimal: A repeated remainder is what marks the cycle.
• Excel sheet column number: Base 26, but with no zero digit.
• Happy number: Cycle detection over sums of squared digits.

What is the time and space complexity of Math and number theory (GCD, sieve, modular)?

varies

GCD costs O(log of the smaller value). A sieve up to 1e7 is fine, but 1e9 is not.