Read two positive whole numbers a and b and print their greatest common divisor. Try Euclid's rule: gcd(a, b) = gcd(b, a % b), and gcd(a, 0) = a.
What to build
A short recursive function based on a very old idea.
Requirements
- Read
aandb. - Print their greatest common divisor.
Input
One line with a and b separated by a space, each from 1 to 1000000.
Output
The greatest common divisor.
Constraints
Each number is from 1 to 1000000.
Example
Input:
12 18
Output:
6
Why it works
Any number that divides both a and b also divides a % b, so the pair can be replaced by a smaller one without changing the answer.
Examples
Example 1 · Input
12 18
Expected output
6
Example 2 · Input
7 5
Expected output
1
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
a % b is the remainder when a is divided by b.
Solution
Show one correct solution (try it yourself first)
def gcd(a, b):
if b == 0:
return a
return gcd(b, a % b)
a, b = input().split()
print(gcd(int(a), int(b)))