Problem
Existe uma outra versão do algoritmo de Euclides, na qual a operação de subtração é substituída pela operação de cálculo do resto.
Esta versão é considerada preferível hoje, pois contém, em média, um número significativamente menor de etapas. No entanto, na época em que os computadores eram grandes e lentos, a operação de divisão podia ser um procedimento complexo em si. E então a primeira versão do algoritmo poderia ser mais eficiente.
Implemente o algoritmo de Euclides substituindo a subtração por uma operação de módulo.
Dois números naturais
A
e
B
são dados. Escreva uma função
nod(A, B)
que retorne o máximo divisor comum de
A
e
B
.
Exemplos de programas
# |
Entrada |
Saída |
1 |
12 42 |
6 |
Lembre-se de que você não pode usar loops em sua solução.
Você só precisa escrever uma função, nada precisa ser inserido e enviado!Запрещенные операторы: for;while;do;until;gcd