N
Man kann den Euklid'schen Algorithmus auf mehrere Zahlen erweitern:
ggT(ggT(a,b),c)=ggT(a,b,c)
Das ist meißtens schneller als Primfaktorzerlegung. Am langsamsten ist der Euklid'sche Algorithmus bei zwei aufeinanderfolgenden Fibonacci-Zahlen(0,1,1,2,3,5,8,13,21,34,...)
Ich hab das nachgeschlagen in: Kleine Enzyklopädie Mathematik
(Klein? Das Teil hat 800 Seiten mit jeweils 60 Zeilen!)