2-12r

Найти наибольший общий делитель (НОД) и наименьшее общее кратное (НОК) двух заданных натуральных чисел.

Наибольший общий делитель (НОД) двух чисел – это самое большое число, которое делит без остатка эти два числа.

Эффективный алгоритм для нахождения наибольшего общего делителя (НОД) двух целых чисел - Алгори́тм Евкли́да. Алгоритм назван в честь греческого математика Евклида, который впервые описал его в VII и X книгах «Начал».

Описание алгоритма нахождения НОД делением

Большее число делим на меньшее.
Если оно делится без остатка, то меньшее число и есть НОД (следует выйти из цикла).
Если есть остаток, то большее число заменяем на остаток от деления.
Переходим к пункту 1.

В нашей программе этот алгоритм осуществляется в строках 9-11. А в 12 строке мы получаем nod:=a1+b1; a1 и b1 по нашему алгоритму являются остатками от деления большего числа на меньшее (пункт 2 алгоритма). Когда очередной остаток равен 0, то другой остаток и есть НОД. А это означает, что и сумма a1+b1 равняется НОД (одно же из слагаемых равно 0). Но оказывается, догадаться до этого не так то просто и этот факт вызывает удивление у большинства начинающих.

Program A2_12;

Var

a,b,a1,b1,nod,nok:integer;

begin

readln(a,b);

if (a=0) and (b=0) then

begin writeln('Oba chisla ravni 0');

readln; exit;

end;

a1:=a; b1:=b;

while (a1<>0) and (b1<>0) do

if(a1>b1) then a1:=a1 mod b1

else b1:=b1 mod a1;

nod:=a1+b1;

nok:=a*(b div nod);

writeln('NOD=',nod,'

NOK=',nok);

readln;

end.

// Program A2.12;

#include <iostream>

using namespace std;

int main()

{

int a,b,a1,b1,nod,nok;

cin>>a>>b;

if(a==0 && b==0)

{cout<<"Oba chisla ravni 0"<<endl;

return 0; }

a1=a; b1=b;

while(a1!=0 && b1!=0)

if(a1>b1) a1=a1%b1;

else b1=b1%a1;

nod=a1+b1;

nok=a*(b/nod);

cout<<"NOD="<<nod<<" NOK="

<<nok<<endl;

return 0;

}