Problem
Il existe une autre version de l'algorithme d'Euclide, dans laquelle l'opération de soustraction est remplacée par l'opération de calcul du reste.
Cette version est considérée comme préférable aujourd'hui, car elle contient, en moyenne, un nombre d'étapes nettement inférieur. Cependant, à l'époque où les ordinateurs étaient gros et lents, l'opération de division pouvait être une procédure complexe en soi. Et puis la première version de l'algorithme pourrait être plus efficace.
Implémentez l'algorithme d'Euclide en remplaçant la soustraction par une opération modulo.
Deux nombres naturels
A et
B sont donnés. Écrivez une fonction
nod(A, B) qui renvoie le plus grand diviseur commun de
A et
B.
Exemples de programmes
| # |
Entrée |
Sortie |
| 1 |
12 42 |
6 |
N'oubliez pas que vous ne pouvez pas utiliser de boucles dans votre solution.
Vous n'avez qu'à écrire une fonction, rien n'a besoin d'être entré et sorti !Запрещенные операторы: for;while;do;until;gcd