Cryptohack Lab. Greatest Common Divisor

Для решения нужно вычислить НОД чисел 66528 и 52920.

Sulution

Подобная задача часто встречается в криптографии, поэтому глупо будет про нее не рассказать. Одним из способов вычисления НОД (наибольшего общего делителя) является алгоритм Евклида.

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

Алгоритм для поиска наибольшего общего делителя.

Если у нас есть два числа a и b, то:

НОД(a, b) = НОД(b, a mod b)

где a mod b — остаток от деления a на b.

Это работает, потому что общий делитель двух чисел также делит их разность и остаток от деления. Реализуем решение на Python:

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


if __name__ == '__main__':
    print(gcd(66528, 52920))

Ответ: 1512