ВВЕРХ
ВНИЗ

Наименьшее общее кратное (НОК)






Следующий код предназначен для нахождения НОК двух чисел. Максимально допустимое значение — 18 446 744 073 709 551 615 (целочисленный тип данных — uint64), поддерживаемое средой PascalABC.Net. Если вы используете другую среду Паскаля, то используйте integer. Смысл приведенного ниже решения исходит из простого классического факта для двух натуральных чисел А и В: произведение A·B равно произведению НОД(А,В) на НОК(А,В). Последнее означает, что наибольшее общее кратное двух чисел можно найти по формуле:

НОК(А,В) = A·(B/НОД(А,В)).

То есть, сначала делим одно из чисел на наибольший общий делитель, а потом результат умножаем на второе число. Как найти НОД двух чисел, смотрим на странице Наибольший общий делитель. Комментарии достаточно понятны:

Код Pascal
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
var
  A, B, x, y, NOK: integer;

begin
  writeln('Введите целые неотрицательные числа A и B:');
  readln(A, B);
  x := A; { <== Запоминаем А }
  y := B; { <== Запоминаем В }
  write('Результат: НОД(', A, ', ', B, ') = ');
  { Сначала находим НОД(А,В): }
  while A <> B do
    if A > B then A := A - B 
    else B := B - A;
  { На выходе из цикла получим НОД = А }
  NOK := x * (y div A); { <== находим НОК(А,В) }
  { Выводим результат: }
  writeln(' ', NOK)
end.

Яндекс.Метрика