Lesson 13 of 16

Reduce Integer Problems with Remainders

You have groups of 24 and 18 items and want equal-size bundles with no leftovers. The largest bundle size is the greatest common divisor (GCD). You need not test every possible divisor.

Euclid’s algorithm

Write a = b × quotient + remainder. Any common divisor of a and b divides the remainder, and any common divisor of b and the remainder divides a. Thus gcd(a, b) = gcd(b, a % b).

def gcd(a, b):
    a, b = abs(a), abs(b)
    while b != 0:
        a, b = b, a % b
    return a

print(gcd(24, 18))
print(gcd(0, 7))

The results are 6 and 7. The first calculation follows (24,18) → (18,6) → (6,0). When the remainder reaches zero, the remaining number is the answer. This function uses absolute values and conventionally returns zero for gcd(0,0).

How far must a prime test search?

A prime is an integer at least 2 with no divisors except 1 and itself. If composite n = a × b, both factors cannot exceed √n. Therefore, test divisors only from 2 through √n. Integer code can express the bound as d*d <= n.

One is not prime. To produce a list of primes, the sieve of Eratosthenes removes multiples of previously found primes. Multiples of p below p² have already been handled by earlier primes.

Keep the input conditions explicit

• Decide whether GCD inputs include zero or negatives.
• Reject values below 2 before primality testing.
• Reducing the divisor range still leaves costs for very large integers. Distinguish iteration counts from the cost of arithmetic on long numbers.

Check your understanding

Why is it wrong to declare 49 prime after testing divisors only from 2 through 6?