Классические НОД и НОК

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

НОД двух целых чисел m и n — это их наибольший общий делитель. Если НОД равен единице, то числа m и n считаются взаимно простыми.

Существует стандартный метод для нахождения НОД:

1. Разложить числа на простые множители.
2. Подчеркнуть одинаковые множители у каждого числа.
3. Перемножить их — и получится НОД.

Однако этот метод не очень эффективен. Разложение каждого числа на простые множители может занять много времени, а вычёркивание общих множителей требует дополнительных усилий. Поэтому мы будем использовать алгоритм Евклида, хотя на самом деле его придумал не Евклид.

Допустим, что m > n. Мы будем строить такую последовательность чисел:

1. q1 — остаток от деления m на n
2. q2 — остаток от деления n на q1
3. q3 — остаток от деления q1 на q2
4. q4 — остаток от деления q2 на q3
5. и т. д., пока не получим нулевой остаток

В математике доказано, что последний ненулевой остаток и есть НОД(m,n).

Вот так выглядит вычисление НОД:

Напишем функцию gcd(m, n), которая возвращает вычисленный НОД двух чисел:

def gcd(m: int, n: int) -> int:
    while n:
        temp = m
        m = n
        n = temp % n
    return m

Обрати внимание: в этом коде не вычисляется максимум чисел m и n. Ранее мы предполагали, что m > n, но здесь это необязательно. Почему? Если первое число меньше второго, они просто поменяются местами на первом шаге алгоритма.

Наименьшее общее кратное (НОК) двух чисел можно найти двумя способами: разложением чисел на простые множители или через НОД по формуле: