208. Greatest Common Divisor by Recursion
Foundation1000 ms256 MBSolved by 0%
Print the greatest common divisor of a and b, the largest number that
divides both exactly.
The recursive rule, which is over two thousand years old, is short:
gcd(a, 0) = a
gcd(a, b) = gcd(b, a % b)
Do not loop from 1 upwards testing every number. With values up to a million that is a million tests; this rule finishes in a handful of steps.
Constraints - `1 ≤ a ≤ 1000000` - `1 ≤ b ≤ 1000000`
Input
A single line containing two integers a and b, separated by a space.
Output
Print one integer, the greatest common divisor of a and b.
Input12 18
Output6
Noteis a small case you can factor by hand
Input17 13
Output1
Noteis two primes, so the answer is 1
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.
Hint 1Where to start
Hint 2The approachOpen hint 1 first. This one carries on from it.
Hint 3PseudocodeOpen hint 2 first. This one carries on from it.
Hint 4Full solutionOpen hint 3 first. This one carries on from it.