Greatest Common Divisor

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

It runs in O(log(min(a, b))) steps, because every two steps at least halve the larger number. The worst case is a pair of consecutive Fibonacci numbers. For numbers up to 10^9 that is at most 43 steps, and the algorithm uses O(1) extra space.

Q: Why does gcd(a, b) equal gcd(b, a % b)?

Write a = q × b + r with r = a % b . A number that divides a and b divides a - q × b , which is r . A number that divides b and r divides q × b + r , which is a . Both pairs have the same common divisors, so they have the same greatest one.

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.

+14 hidden tests on Submit

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

The definition suggests trying candidates one by one, and that works on small numbers. With a and b up to 10^9, though, two large numbers that share no factor force a billion tries. Euclid's observation that gcd(a, b) equals gcd(b, a % b) shrinks the numbers 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 be larger than the smaller of the two numbers, because a divisor of b is at most b. So start a candidate d at min(a, b) and move it down by one until it divides both. Since you try the candidates from the top, the first one that works is the greatest.

For 12 and 18 you try 12 (it does not divide 18), then 11, 10, 9, 8 and 7, which fail, and stop at 6. The loop always ends, because 1 divides everything.

The cost is the number of candidates. For 999999937 and 999999929, two primes, the answer is 1 and the loop runs almost 10^9 times. That is far too slow for the largest tests.

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, where r = a % b. Any number that divides both a and b also divides r = a - q × b. Any number that divides both b and r also divides a = q × b + r. So the pairs (a, b) and (b, r) have exactly the same common divisors, and the same greatest one.

Replace (a, b) with (b, a % b) and repeat until b becomes 0. Every number divides 0, so gcd(a, 0) = a and a is the answer. For 12 and 18: (12, 18) becomes (18, 12), then (12, 6), then (6, 0), and the answer is 6. The first step swaps the numbers on its own when a is smaller, so you never need to sort them.

Every two steps at least halve the larger number, so the loop runs O(log(min(a, b))) times. The slowest inputs are consecutive Fibonacci numbers such as 701408733 and 433494437, and even they take only 42 steps.

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

The algorithm is short, so the bugs come from the update and the stopping condition.

Updating in the wrong order. a = b followed by b = a % b computes b % b, which is always 0, and returns b. Save the remainder in a temporary first, or assign both at once.
Returning b instead of a when the loop ends. At that point b is 0.
Stopping the countdown at 2 or starting it at max(a, b). The first misses coprime pairs such as 17 and 5; the second wastes time on candidates that cannot divide the smaller number.
Using repeated subtraction instead of the remainder. gcd(10^9, 1) then takes a billion subtractions; % does them all in one step.

Frequently asked questions4

What is the time complexity of Euclid's algorithm?

It runs in O(log(min(a, b))) steps, because every two steps at least halve the larger number. The worst case is a pair of consecutive Fibonacci numbers. For numbers up to 10^9 that is at most 43 steps, and the algorithm uses O(1) extra space.

Why does gcd(a, b) equal gcd(b, a % b)?

Write a = q × b + r with r = a % b. A number that divides a and b divides a - q × b, which is r. A number that divides b and r divides q × b + r, which is a. Both pairs have the same common divisors, so they have the same greatest one.

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 once you have the gcd, the lcm is a / gcd(a, b) × b.

What is the gcd of two coprime numbers?

Two numbers are coprime when their greatest common divisor is 1, meaning they share no prime factor. Two different primes are always coprime, and so are any two consecutive integers, such as 8 and 9.