Наибольший общий делитель

Как несложно догадаться, наибольший общий делитель (англ. greatest common divisor) двух целых чисел - наибольшее число, на которое делится каждое из них. Например:

Сразу заметим важное свойство:

НОД играет большую роль как в математике, так и в программировании, и часто встречается в задачах на различные темы.

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

Алгоритм Евклида - один из первых алгоритмов в истории, использовался ещё в Древней Греции, и дошёл до наших дней. В изначальном виде он назывался “взаимным вычитанием”, так как заключался в поочерёдном вычитании меньшего числа из большего, пока одно из них не станет равным 0. Сегодня чаще всего вместо вычитания используется взятие остатка от деления, но суть алгоритма сохранилась.

Алгоритм заключается в построении ряда чисел следующего вида ():

Где каждое последующее число является остатком от деления предпредыдущего на предыдущее:

Ряд заканчивается, когда остаток от деления предпоследнего числа на последнее становится равным 0:

В таком случае утверждается, что:

Для доказательства этого утверждения сначала докажем следующее: наборы общих делителей пары и пары полностью совпадают. Рассмотрим произвольный (не обязательно наибольший) общий делитель и :

- общий делитель и .

, или .

Докажем, что также является общим делителем и .

делится на по определению.

, где и целые по определению.

Значит, также делится на , что и требовалось доказать.

Из того, что все общие делители пар и совпадают, в частности следует, что .

Далее по индукции можно доказать следующее:

(Нуль в последнем выражении появился из условия ).

Нуль делится на все числа, отличные от нуля, поэтому справедливо следующее свойство:

Следовательно,

что и требовалось доказать.

Варианты реализации алгоритма Евклида на C++

Существует несколько вариантов реализации алгоритма Евклида, как итеративных так и рекурсивных. Классическая итеративная реализация (работающая быстрее всех рекурсивных) выглядит так:

1
2
3
4
5
6
7
8
9
10
11
12
int gcd(int a, int b) {
    if (a < b) {
        swap(a, b);
    }

    while (b) {
        a %= b;
        swap(a, b);
    }

    return a;
}

Рекурсивно это же можно реализовать так:

1
2
3
4
5
6
7
8
9
10
11
int gcd(int a, int b) {
    if (a < b) {
        swap(a, b);
    }

    if (b) {
        return gcd(b, a % b);
    } else {
        return a;
    }
}

Преимущество рекурсивной реализации заключается в возможности записать её в очень кратком виде (предполагающим, что ):

1
2
3
int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

На практике разница во времени работы итеративного и рекурсивного вариантов не столь значительна, так что вы можете использовать любой из них.

Время работы алгоритма Евклида

Согласно некоторым исследованиям, время работы алгоритма Евклида тесно связано с числами Фибоначчи. Это выражается, в частности, в том, что два последовательных числа Фибоначчи - наихудшие входные данные для алгоритма Евклида. При , алгоритм Евклида совершит ровно итерации. Отсюда можно выразить асимптотическую сложность алгоритма: последовательность Фибоначчи возрастает с экспоненциальной скоростью, поэтому алгоритм Евклида работает за .

Наименьшее общее кратное

С понятием НОД связано также понятия наименьшего общего кратного (англ. least common multiple). Наименьшее общее кратное двух натуральных чисел - наименьшее натуральное число, которое делится на каждое из них. Оно обозначается следующим образом:

и связано с НОД формулой:

Реализация на C++:

1
2
3
4
5
int lcm(int a, int b) {
    return a / gcd(a, b) * b;   //используя форму a * b / gcd(a, b),
                                //можно получить переполнение на этапе a * b,
                                //поэтому следует выполнять деление до умножения
}

Взаимнопростые числа

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

НОД и НОК для произвольного количества чисел

Обе функции легко обобщаются для произвольного числа аргументов последовательным применением: