Найти наименьшее общее кратное (НОК), используя алгоритм НОД

16 ноября 2009

Сегодня мы поговорим о наименьшем общем кратном (НОК) двух чисел и как его найти. НОК – это целое число, которое делится на два любых целых числа. Например, даны два числа 2 и 3, НОК этих чисел равен 6, т.е. число 6 делится и на 2 и на 3.
Чтобы написать данную программу на C# будем использовать ко всему прочему алгоритм Евклида нахождение НОД. Лучше всего реализовать алгоритм в рекурсивной функции.

int nod_recur(int num1, int num2)
{
	int n = num1 % num2;
	num1 = num2;
	num2 = n;
	if (n > 0)
		return nod_recur(num1, num2);
	else
		return num1;
}

Как работает эта функция, я рассказывать не буду, т.к. вы можете прочитать это в другой моей статье, посвященной этому алгоритму. Ну и собственно код процедуры события клика по кнопке “button1”:

private void button1_Click(object sender, EventArgs e)
{
	int num1 = Convert.ToInt32(n1.Text);
	int num2 = Convert.ToInt32(n2.Text);
	n_nok.Text = Convert.ToString(num1 * num2 / nod_recur(num1, num2));
}

Как вы видите из кода, здесь происходит считывание двух введенных чисел в переменные и вычисление НОК. Можно сказать, что НОК вычисляется в два действия: перемножаются два и результат от умножения делится на результат вычисления НОД этих двух чисел. Результат вычисления НОК записывается в текстовое поле “n_nok”.

Вы думали, что написать такую программу будет не так просто? Извините, что разочаровал вас. В другой статье, я расскажу вам, как вычислить НОК для двух и более чисел, так называемый универсальный алгоритм.

Автор: Евтеев Евгений Александрович