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

Наибольший общий делитель двух чисел – наибольшее число, на которое делится каждое из них. Например, НОД(12,18) = 6 НОД(10,22) = 2. Роль наибольшего общего делителя трудно переоценить – он играет большую роль в математике, информатике и т.д. Также с понятием НОДа связано понятие Наименьшего Общего Кратного (НОК). Наименьшее общее кратное двух натуральных чисел - наименьшее натуральное число, которое делится на каждое из них без остатка. НОД и НОК связаны следующим соотношением:

\[НОК(a, b) = \frac{a * b}{НОД(a, b)}\]

Например, НОК(22,66) = 66

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

Мы приведем две формы реализации данного алгоритма: рекурсивную и итеративную. Разница между двумя этими реализациями не столь значительна, поэтому можно на практике использовать обе. Классическая (итеративная) реализация:

int gcd(int a, int b)
{
        while (a != b)
	{
		if (a > b)
			a -= b;
		else
			b -= a;
	}
	return a;
}

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

int gcd(int a, int b)
{
        while (b != 0)
	{
		a %= b;
		swap(a, b);
	}
	return a;
}

Рекурсивная реализация:

int gcd(int a, int b)
{
	return (b == 0) ? abs(a) : gcd(b, a % b);
}

Используя формулу связи НОД и НОК (дана выше) нетрудно вывести функцию для НОК.

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

Наихудшим случаем для алгоритма Евклида являются числа Фибоначчи. При a=Fn,b=Fn−1, алгоритм Евклида совершит ровно n−2 итерации. Сложность алгоритма Евклида: \(O(\log \min(a, b))\).