Greatest Common Divisor

Q: What is the time complexity of Euclid's algorithm?

O(log(min(a, b))) steps and O(1) space. The slowest inputs are consecutive Fibonacci numbers: 701408733 and 433494437 take 42 steps, or 43 with the smaller first, the most for any pair up to 10^9 .

Q: What is the gcd of two coprime numbers?

It is 1 : two numbers are coprime exactly when they share no prime factor. Two different primes are always coprime, and so are two consecutive integers such as 8 and 9 .

BeginnerMath and simulation

+10

You get two positive integers a and b. Return their greatest common divisor: the largest integer that divides both of them with no remainder.

For example, the numbers that divide both 8 and 12 are 1, 2 and 4, so the answer is 4.

Function

gcd(a: integer, b: integer) → integer

ainteger: the first positive integer
binteger: the second positive integer
Returnsinteger: the largest integer that divides both a and b

Constraints

1 ≤ a ≤ 10⁹
1 ≤ b ≤ 10⁹

Examples

Input: a = 12b = 18
Output: 6
Explanation: The divisors of 12 are 1, 2, 3, 4, 6 and 12; the divisors of 18 are 1, 2, 3, 6, 9 and 18. The largest one on both lists is 6.

Input: a = 17b = 5
Output: 1
Explanation: 17 and 5 are both prime and different, so the only divisor they share is 1.

Input: a = 42b = 42
Output: 42
Explanation: A number divides itself, and nothing larger than 42 can divide 42, so the greatest common divisor of 42 and 42 is 42.

Follow-up

Can you extend Euclid's algorithm to also return integers x and y with a × x + b × y = gcd(a, b)?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Trying candidates one by one works on small numbers, but two numbers near 10^9 that share no factor force a billion tries. Euclid's rule gcd(a, b) = gcd(b, a % b) shrinks the pair so fast that no pair up to 10^9 needs more than 43 steps.

Count down from the smaller number

Correct, but does not finish on the largest tests

Intuition

No common divisor can exceed the smaller number. Start d at min(a, b) and move it down by one until it divides both. Since you go from the top, the first hit is the greatest, and the loop always stops by 1. For 12 and 18 you try 12 down to 7 and stop at 6.

The cost is one try per candidate. For the primes 999999937 and 999999929 the answer is 1, so the loop runs almost 10^9 times.

Algorithm

Set d to the smaller of a and b.
While a % d or b % d is not 0, subtract 1 from d.
Return d.

def gcd(a, b):
    d = min(a, b)
    while a % d != 0 or b % d != 0:
        d -= 1
    return d

Euclid's algorithm

Intuition

Write a = q × b + r with r = a % b. A number that divides a and b also divides r = a - q × b, and a number that divides b and r also divides a = q × b + r. So (a, b) and (b, r) have the same common divisors, and the same greatest one.

Repeat until b is 0. Every number divides 0, so gcd(a, 0) = a. For 12 and 18 the pair goes (12, 18), (18, 12), (12, 6), (6, 0), and the answer is 6. When a is smaller, the first step swaps the pair, so you never sort.

Every two steps at least halve the larger number, so the loop runs O(log(min(a, b))) times.

Algorithm

While b is not 0, compute r = a % b.
Set a = b and b = r.
When b reaches 0, return a.

def gcd(a, b):
    # gcd(a, b) == gcd(b, a % b), and gcd(a, 0) == a.
    while b != 0:
        a, b = b, a % b
    return a

Pitfalls and edge cases

Updating in the wrong order. a = b followed by b = a % b computes b % b, always 0. Save the remainder first, or assign both at once.
Returning b when the loop ends. At that point b is 0.
Stopping the countdown at 2. Coprime pairs such as 17 and 5 then find no answer.
Repeated subtraction instead of the remainder. gcd(10^9, 1) then takes a billion subtractions; one % does them all.

Frequently asked questions3

What is the time complexity of Euclid's algorithm?

O(log(min(a, b))) steps and O(1) space. The slowest inputs are consecutive Fibonacci numbers: 701408733 and 433494437 take 42 steps, or 43 with the smaller first, the most for any pair up to 10^9.

What is the difference between GCD and LCM?

The greatest common divisor is the largest number that divides both inputs; the least common multiple is the smallest number both inputs divide. They are linked by gcd(a, b) × lcm(a, b) = a × b, so the lcm is a / gcd(a, b) × b.

What is the gcd of two coprime numbers?

It is 1: two numbers are coprime exactly when they share no prime factor. Two different primes are always coprime, and so are two consecutive integers such as 8 and 9.