Problem
Donald Knuth, autor de “
A Arte da Programação”, considera o algoritmo de Euclides o primeiro. Porque, apesar do algoritmo ter sido inventado e usado antes mesmo de
Euclides, que viveu nos séculos IV-III . AC (já mencionado por
Aristóteles, que viveu um século antes), Euclides descreve o processo iterativamente, que é consistente com o significado moderno da palavra "algoritmo".
"Substitua o maior dos dois números pela diferença entre o maior e o menor até que sejam iguais. Isso é GCD."
O próprio algoritmo de Euclides é familiar para qualquer aluno moderno. A descrição matemática pode ser visualizada
aqui. Implemente o
clássico Algoritmo de Euclides e formate-o como uma função
nod(a, b) que recebe 2 números como entrada e retorna o maior divisor comum desses dois números.
Nenhuma entrada ou saída é necessária! Você só precisa implementar a função.
Запрещенные операторы: gcd;%