GCD - Greatest Common Divisor: Definition, Examples, Calculator

gcd (наибольший общий делитель) - это наибольшее число, которое может делить два целых числа без остатка.

Решением задачи нахождения gcd является алгоритм Евклида. Этот алгоритм основан на простом наблюдении, что если r - остаток от деления a на b, то gcd(a,b) = gcd(b,r).

Таким образом, мы можем продолжать делить меньшее число на остаток, пока остаток не станет равным 0. В этот момент остаток является наибольшим общим делителем.

Вот пример кода на Python для реализации этого алгоритма:

python
def gcd(a, b):
    while b != 0:
        r = a % b
        a = b
        b = r
    return a

Теперь мы можем вызывать эту функцию для нахождения gcd двух чисел:

python
>>> gcd(12, 8)
4

Вот еще несколько примеров:

python
>>> gcd(16, 12)
4
>>> gcd(5, 7)
1
>>> gcd(24, 36)
12

Как видим, алгоритм работает для разных пар чисел и находит наибольший общий делитель.