Vous devez vous connecter pour exécuter votre code.
Hoare 5 — pgcd (Euclide)
Écrivez le code C de l'algorithme d'Euclide pour le PGCD avec annotations Hoare.
Invariant attendu :
pgcd(a, b) = pgcd(a_initial, b_initial) && a > 0 && b >= 0
Quantité de contrôle attendue :
b
#include <stdio.h>
// @pre: a > 0 && b > 0
// @post: retourne pgcd(a_initial, b_initial)
// @invariant: pgcd(a, b) = pgcd(a_initial, b_initial) && a > 0 && b >= 0
// @variant: b
int pgcd(int a, int b) {
while (b != 0) {
int r = a % b;
a = b;
b = r;
}
return a;
}
int main() {
int a, b;
scanf("%d %d", &a, &b);
printf("%d\n", pgcd(a, b));
return 0;
}