Problem
Donald Knuth, author of “
The Art of Programming”, considers Euclid's algorithm the first ever. Because, despite the fact that the algorithm was invented and used even before
Euclid, who lived in the IV-III centuries . BC (it is already mentioned by
Aristotle, who lived a century earlier), Euclid describes the process iteratively, which is consistent with modern meaning of the word "algorithm".
"Replace the larger of the two numbers with the difference between the larger and smaller until they are equal. This is GCD."
The Euclid algorithm itself is familiar to any modern schoolchildren. Mathematical description can be viewed
here. Implement
classic Euclid algorithm and format it as a function
nod(a, b) that takes 2 numbers as input and returns the greatest common divisor of these two numbers.
No input or output required! You only need to implement the function.
Запрещенные операторы: gcd;%