Euklid und Stein iterativ
# steinscher Algorithmus zur Berechnung des ggt, iterativ
def ggt_iter(a, b):
f=0
while b!=0:
if a<b:
a, b = b, a
else:
if a&1==0: # a gerade
a>>=1
if b&1==0:
b>>=1
f+=1
else: # a ungerade
if b&1==0:
b>>=1
else:
a-=b
return a<<f