5.15 · exercise
gcd, the Euclid way
Euclid noticed around 300 BC that the greatest common divisor of two numbers does not change when you replace the larger with the remainder of dividing it by the smaller. Keep doing that and one of them hits zero; the other is the answer.
The stdin box holds Euclid's own example pair, 1071 and 462, and the starter reads them. Write the loop: get the remainder with udiv and msub, move the second value into the first and the remainder into the second, and repeat while the second value is not zero.
What is checked
- the gcd is printed on its own line
- the program exits cleanly
- the remainder loop does the work (
udiv,msub, and the answer not written in) - the same holds for other pairs you do not see, in either order, with a zero among them
specification
stdin1071 462
stdoutprints the right output
exitexits with the right code
sourceuses
udivsourceuses
msubsourcedoes not hardcode the answer
hiddenright output and exit code on 5 more inputs you do not see
We run your program on the input above and on the hidden ones, and compare what it does. Nothing is matched against a stored solution.