GCD of Two Numbers
GCD of Two Numbers
The greatest common divisor of two positive integers is the largest number that divides both of them exactly. The GCD of 12 and 18 is 6.
Given a and b, print their GCD.
If the two numbers share no factor other than 1, the answer is 1.
Euclid's algorithm is the short way: while b is not zero, replace the pair (a, b) with (b, a % b). When b becomes zero, a is the GCD.
A single line with two space-separated integers a and b.
A single integer: the GCD of a and b.
1 <= a, b <= 10^9
12 18
6
6 divides both 12 and 18, and nothing larger does.
Submit runs your code against 6 test cases — the 1 shown above plus 5 hidden ones covering the awkward cases. Run sample just tries the first example, which is usually what you want while you are still working it out.