yeolyi.comSeongyeol's CS

GCD and Primes

To reduce a 1,920 × 1,080 screen resolution to the smallest whole-number ratio like 16:9, divide both numbers by the largest number that divides both evenly. Checking one by one from 1 to 1,080 whether it divides both numbers finds the largest, 120, after 1,080 checks. Can we find it faster?

The Euclidean algorithm

A number that divides both numbers evenly is called a common divisor, and the largest of them is the greatest common divisor (GCD).

The Euclidean algorithm replaces (a, b) with (b, a mod b) again and again until a mod b, the remainder of dividing a by b, is 0. The b at that point is the GCD.

Let q be the quotient and r the remainder of dividing a by b.

a = b × q + r

We may replace (a, b) with (b, r) because the two pairs have the same common divisors. If d is a common divisor of a and b, we can write a = d × x and b = d × y, so r is a multiple of d too.

r = a − b × q = d × (x − y × q)

Conversely, if d is a common divisor of b and r, with b = d × y and r = d × z, then a is a multiple of d too.

a = b × q + r = d × (y × q + z)

Since the two pairs have exactly the same common divisors, the largest of them, the GCD, is the same too.

a
b
0 modulo operations

Start from (1,920, 1,080).

Each row’s b and r become the next row’s a and b.

What took 1,080 checks now takes 4 modulo operations. It finishes quickly because a mod b is always less than half of a. If b is at most half of a, the remainder is less than b; if b is more than half, the remainder is a − b. So every two divisions the larger number drops below half, and the algorithm needs only O(log a) modulo operations.

The sieve of Eratosthenes

To find all primes up to 100, we could divide each number, but crossing numbers out is faster. Keep 2 and cross out all multiples of 2. Keep 3, the next number not crossed out, and cross out the multiples of 3. The smallest number not yet crossed out isn’t divisible by any smaller prime, so it is prime. This method is called the sieve of Eratosthenes.

0 crossed out

1 isn't prime, so skip it and start from 2.

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100

Highlighted cells are the prime kept in this step, and struck-through cells are crossed out.

The multiples of p are crossed out starting from p × p. Smaller multiples like p × 2 and p × 3 are multiples of smaller primes, so they are already crossed out. That’s why we can stop once 11 × 11 is past 100.

Wrapping up

As we saw in the search post, the same task can run at very different speeds depending on how the data is organized. So the next part covers data structures, ways to lay out many values in memory, one by one. The first post is Arrays.

Challenge

Applying the Euclidean algorithm to two integers a > b ≥ 1 repeats the modulo operation until the remainder is 0. Among the cases that take exactly 7 modulo operations, what is a when it is smallest? Answer with a number.