алгоритм Евклида на python

Алгори́тм Евкли́да — эффективный алгоритм для нахождения наибольшего общего делителя двух целых чисел.

Подробнее об алгоритме читаем на википедии.

Пример реализации на python:

def evc(a, b):

    if a < b:

        a, b = b, a

    r = 1

    while r > 0:

        r = a % b

        a = b

        b = r

    return a