Вариант 1
var a,b:longint;
function NOD(x,y:longint):longint; { функция поиска наиб. общ. делителя }
begin
if x<>0 then NOD:=NOD(y mod x,x) else NOD:=y;
end;
function NOK(x,y:longint):longint; { функция поиска наим. общ. кратного }
begin
NOK:=( x div NOD(x,y) ) * y;
end;
begin { основная программа }
readln(a,b);
writeln( 'НОД этих чисел = ', NOD(a,b) );
writeln( 'НОК этих чисел = ', NOK(a,b) );
end.
Вариант 2 Переборный алгоритм
var a, b, d: integer;
begin
write('Введите два числа: ');
readln(a, b);
if a < b then d := a + 1 else d := b + 1;
{так как мы используем цикл с постусловием, необходимо минимальное значение увеличить на один,
иначе цикл repeat, в силу своих конструктивных
особенностей, не учтет это минимальное число и
не сделает его кандидатом в НОД. Например, 5 и 25.}
repeat d := d - 1
until (a mod d = 0) and (b mod d = 0);
write('NOD = ', d)
end.
Вариант 3
var
m,n,r:integer;
label lb;
begin
write('Введите первое число:');readln(m);
write('Введите второе число:');readln(n);
lb:r:=m mod n;
if r=0 then writeln('НОД = ',n)
else
begin
m:=n;
n:=r;
goto lb;
end;
end.
Вариант 4 Алгоритм Евклида с вычитанием
Пусть 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) дает нам понять, когда надо остановиться.
var a, b: integer;
begin
write('a = ');
readln(a);
write('b = ');
readln(b);
while a <> b
do if a > b then a := a - b else b := b - a;
writeln('NOD = ', a);
end.
Вариант 5 Алгоритм Евклида с делением
Пусть a и b — целые числа, а r — остаток от деления a на b. Тогда НОД(a, b) = НОД(b, r). Эта формула также позволяет свести вычисление наибольшего общего делителя одной пары чисел к вычислению наибольшего обшего делителя другой пары чисел.
var a, b: integer;
begin
write('a = ');
readln(a);
write('b = ');
readln(b);
while (a <> 0) and (b <> 0)
do if a >= b then a := a mod b else b := b mod a;
write(a + b)
end.
Вариант № 6
Program test2(input,output);
Const N = 5;
Var
С: array[1..5] of integer;
A,B:integer;
function HOК (A, В:integer):integer;
begin
HOK:=A*B/ HOD(A,B);
end;
function НОD(А, В:integer):integer;
var
X,Y:integer;
begin
X:= A; Y: = В;
1:IF X = Y THEN HOD:=X;
IF X > Y THEN begin
X:= X – Y;goto 1;
end;
IF Y > X THEN begin
Y:= Y – X;goto 1;
end;
end;
Begin
FOR i= 1 ТО N READ (C[i]);
A:= С ([l])
FOR i = 1 TO N–1 begin B:=С[i + 1];
A:= HOK(A,B);
end;
writeln ("HOK="; A);
end.
Вариант 7
Program N_O_D (Input, Output);
Var
A, B: LongInt;
NOD : LongInt;
Begin
WriteLn ('PASCAL: Нахождение Н.О.Д. двух заданных чисел.');
Writeln ('Введите числа, для которых ищется НОД:');
Write('Первое число: ');ReadLn (A);
Write('Второе число: ');ReadLn (B);
If (A < B)ThenNOD := A Else NOD := B;
While Not( (A mod NOD = 0) and (B mod NOD = 0) ) do
NOD := NOD - 1;
WriteLn ('НОД = ',NOD);
ReadLn;
End.
Program N_O_D (Input, Output);
Var
A, B: LongInt;
NOK, NOD : LongInt;
Begin
WriteLn ('PASCAL: Нахождение Н.О.К. двух заданных чисел.');
WriteLn ('Введите числа, для которых ищется НОК:');
Write ('Первое число: ');ReadLn (A);
Write ('Второе число: ');ReadLn (B);
If (A < B)ThenNOD := A Else NOD := B;
While Not ( (A Mod NOD = 0) And (B Mod NOD = 0) ) Do
NOD := NOD - 1;
A := A Div NOD;
B := B Div NOD;
NOK := A * B * NOD;
WriteLn ('НОК = ', NOK);
ReadLn;
End.