GCD - Euclid’s algorithm
After running several iterations of the algorithm, we start to notice that there are some redundant operations, and the algorithm of finding the greatest common divisor can actually be optimized.
With subtraction, we keep subtracting the smaller number from the larger number until we get a result of 0 or a number that is equal to the GCD. We can speed that up by finding the remainder of the larger number divided by the smaller one. With the modulo operation, we keep dividing the larger number by the smaller number and taking the remainder until the remainder is 0. The last non-zero remainder we get is the GCD.
Think of the modulo operation as a more efficient way of finding the GCD. Instead of subtracting the smaller number from the larger number repeatedly, you are using division to reduce the larger number. This means that you are dividing both numbers by their common divisors and so converging to the greatest common divisor much faster.
a, b = int(input()), int(input())
while a > 0 and b > 0: # In case a or b is 0 => the other one is the GCD
a, b = b, a % b # gcd of (a, b) is the same as gcd of (b, a % b)
d = b if a == 0 else a # if a is 0 => b is GCD, if b is 0 => a is GCD
print('gcd:', d)This algorithm was first mentioned in Euclid’s book written in 300 BC.
Let’s run several simulations of the algorithm:
a = 8, b = 12
- a = 12, b = 8
- a = 8, b = 4
- a = 4, b = 0
- break ⇒ GCD = 4
a = 54, b = 24
- a = 24, b = 6
- a = 6, b = 0
- break ⇒ GCD = 6
a = 17, b = 16
- a = 16, b = 1
- a = 1, b = 0
- break ⇒ GCD = 1
Input
The only line of the input contains two integers
a and b (0 ≤ a, b ≤ ).Output
The program should print the greatest common divisor of
a and b.Examples
Input | Output |
8 12 | 4 |
54 24 | 6 |
17 16 | 1 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB