gcd

Алгоритм Евклида находит наибольший общий делитель (НОД) двух целых чисел за O(log min(a, b)) операций. Это один из старейших известных алгоритмов — он описан ещё в «Началах» Евклида около 300 г. до н. э. — и при этом остаётся рабочим инструментом в криптографии, сокращении дробей и вычислении...