MyTetra Share
Делитесь знаниями!
Алгоритм Евклида (НОД)
Время создания: 19.07.2017 20:16
Раздел: Math

Наибольший общий делитель


Большее число а делится с остатком на меньшее число b;

Если остаток r1 от деления равен 0, то число b и есть НОД;

Если r1 != 0, то число b делится на r1.

Если остаток r2 == 0, то r1 есть НОД;

Если остаток r2 != 0, то r1 делится на r2;

И т.д., пока остаток не будет равен нулю.




#include <iostream>

using namespace std;


int main()

{

int x, y;

cin >> x >> y;


if(x == y)

{

cout << x;

}

else if(x == 0 && y!= 0)

{

cout << y;

}

else if(x != 0 && y == 0)

{

cout << x;

}

else

{

int dividend = 0;

int divider = 0;

int reminder = 0;


if(x > y)

{

dividend = x;

divider = y;

}

else

{

dividend = y;

divider = x;

}


reminder = dividend % divider;

while(reminder!=0)

{

dividend = divider;

divider = reminder;

reminder = dividend % divider;

}

cout << divider;

}


system("pause");

return 0;

}

Так же в этом разделе:
 
MyTetra Share v.0.53
Яндекс индекс цитирования