Основы алгоритмов (Одаренность)

Алгоритм Евклида нахождения НОД

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

Доказательство корректности

Пусть k — любой общий делитель чисел a и b, не обязательно наибольший, тогда a = t_1 \cdot k ; b = t_2 \cdot k; где t_1 и t_2 — целые числа из определения.

Тогда k является также общим делителем чисел b и r, так как b делится на k по определению, а r = a - bq = (t_1 - t_2\cdot q)\cdot k (выражение в скобках есть целое число, следовательно, k делит r без остатка)

Обратное также верно и доказывается аналогично пункту 2: любой делитель b и r так же является делителем a и b.

Следовательно, все общие делители пар чисел (a, b) и (b, r) совпадают. Другими словами, нет общего делителя у чисел (a, b), который не был бы также делителем (b, r), и наоборот.

В частности, наибольший общий делитель остается тем же самым. Что и требовалось доказать. --

Еще варианты реализации

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

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

НОК (LCM)

Алгоритм нахождения LCM

lcm(a,b) = a*b / gcd(a,b)

Программная реализация алгоритма нахождения LCM

int lcm (int a, int b) {
	return a / gcd (a, b) * b;
}