Loading...
Loading...
Loading...
A tiling team has a hall that is a metres long and b metres wide. They want the largest square tile, with a whole number of metres on each side, that covers the floor exactly with no cutting.
That side is the greatest common divisor (GCD) of a and b. Given a and b, print it.
Example 1
Input
48 18
Output
6
The largest tile has side 6.
Example 2
Input
7 13
Output
1
No common divisor except 1.
Try the problem first. Open one hint at a time.
Euclid's idea: the GCD of a and b is the same as the GCD of b and the remainder of a divided by b.
Repeat that step in a while loop until the remainder is 0. The last non-zero value is the answer.
Write your Python code, run it on the examples and submit it to hidden tests.
Solve in the editor