Найти наименьшее общее кратное двух натуральных чисел
Формулировка. Даны два натуральных числа. Найти их наименьшее общее кратное.
Примечание: наименьшим общим кратным двух чисел m и n называется наименьшее натуральное число, которое делится на m и n. Обозначение: НОК(m, n)
Решение. Из теории чисел известно, что НОК(m, n) связан с НОД(m, n) следующим образом:
Следовательно, для нахождения ответа нам нужно лишь использовать предыдущую задачу нахождения НОД двух чисел m иn:
while m <> n do begin
if m > n then begin
Так как исходные переменные будут испорчены в процессе работы алгоритма Евклида, нам нужно вычислить их произведение до входа в описанный выше цикл и присвоить это произведение переменной prod (от англ. product – «произведение»):
После этого нам остается вывести на экран результат арифметического выражения в правой части нашей формулы. В качестве самого НОД будет использоваться переменная m:
writeln(prod div m);
Кстати, деление в формуле будет целочисленным (через div) именно потому, что если два числа делятся на некоторое число, то и их произведение также делится на него.
Нахождение НОД и НОК двух чисел — Pascal(Паскаль)
Пусть a и b — целые числа, тогда верны следующие утверждения:
Все общие делители пары a и b являются также общими делителями пары a — b, b;
И наоборот, все общие делители пары a — b и b являются также общими делителями пары a и b; НОД(A, B) = НОД(A — B, B), если A > B; НОД(A, 0) = A.
Если t — произвольный общий делитель a и b, то он делит и разность a — b. Действительно, из a = t * u и b = t * v следует, что a — b = t * u — t * v = t * (u — v). То есть t — также общий делитель а — b и b. Обратно, если t — произвольный делитель общий делитель a — b и b, то он делит и их сумму a — b + b = a. Это можно доказать аналогично предыдущему. Поэтому t — также общий делитель a и b. Делаем вывод, что множество общих делителей a и b совпадает с множеством делителей a — b и b. В частности, совпадают и наибольшие общие делители этих пар. Наибольшее целое, на которое делится число a, есть само число а. Число 0 делится на любое число. Отсюда наибольший общий делитель а и 0 равен а. Доказанная формула(3) позволяет свести вычисление наибольшего делителя одной пары к вычислению наибольшего общего делителя другой пары, в которой числа уже меньше. Очевидная же формула (4) дает нам понять, когда надо остановиться.
Вариант 5 Алгоритм Евклида с делением
Пусть a и b — целые числа, а r — остаток от деления a на b. Тогда НОД(a, b) = НОД(b, r). Эта формула также позволяет свести вычисление наибольшего общего делителя одной пары чисел к вычислению наибольшего обшего делителя другой пары чисел.
Составьте программу нахождения наименьшего общего кратного (НОК) двух чисел, используя формулу
Учебник по Информатике 9 класс Семакин
Составьте программу нахождения наименьшего общего кратного (НОК) двух чисел, используя формулу: А*В = НОД(А, В)*НОК(А, В). 
Program zad_3_nica;
var A, B, C: real;
begin
write (‘Введите A: ‘);
read (A);
write (‘Введите B: ‘);
read (B);
C:=A*B;
while (A<>B)
do begin
if A>B
then A:=A-B
else B:=B-A
end;
C:=C/A;
writeln (‘НОК(A,B)=’, C)
end.
Программа для НОК и НОД на Паскале
Здесь приведен код программы на языке Паскаль. Программа вычисляет НОД и НОК с использованием алгоритма Евклида.
Наибольшим общим делителем (НОД) для двух целых чисел m и n называется наибольший из их общих делителей. Приведем пример: для чисел 70 и 105 наибольший общий делитель будет равен 35. НОД существует и однозначно определён, если хотя бы одно из чисел m или n не ноль.
Наименьшее общее кратное (НОК) двух целых чисел m и n есть наименьшее натуральное число, которое делится на m и n. Например, для 3 и 5, НОК равен 15, а для 2 и 4 НОК равен 4.