Algorithmus von Euklid

input: a >= 1, b >= 1;   // a = A, b = B
while (a /= b) { 
  // Invariante: gcd(a,b) = gcd(A,B)
  // Variante: max (a,b)
  if a > b then a := a - b else b := b - a
} 
output: a     // a = gcd(A,B)
Beweis:



Johannes Waldmann 2015-12-11