Наибольшим общим делителем (НОД) для двух целых чисел m и n называется наибольшее число, на которое делятся числа m и n.
Наибольший общий делитель существует и однозначно определён, если хотя бы одно из чисел m или n не равно нулю.
Алгоритм был придуман Евклидом в Древней Греции более 2000 лет назад и основан на следующем правиле.
Для любых целых чисел x, y > 0 выполняется равенство
НОД (x,\ y) = НОД (x \% y,\ y)
Любое число, которое делит оба числа x и y, делит также и x — y, поэтому
НОД (x,\ y) ≤ НОД (x\ -\ y,\ y).
Аналогично, любое число, которое делит оба числа x\ -\ y и y, делит также и их сумму x, поэтому
НОД (x,\ y) ≥ НОД (x\ -\ y,\ y).
Требуемое равенство получается последовательным вычитанием y из x.
Идея алгоритма отыскания наибольшего общего делителя заключается в том, чтобы отнимать от большего меньшее, пока числа не станут равны. Полученное число и является наибольшим общим делителем.
Например, необходимо определить наибольший общий делитель чисел 50 и 20.
- находим 50-20=30. Из трех чисел 50, 20, 30 отбрасываем наибольшее.
- находим 30-20=10. Из трех чисел 30, 20, 10 отбрасываем наибольшее.
- находим 20-10 = 10. Из трех чисел 20, 10, 10 отбрасываем наибольшее.
- 10=10, значит это число является наибольшим общим делителем исходных.
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
using namespace std;
// Функция нахождения НОД
int NOD(int n1, int n2)
{
int div;
if (n1 == n2) // если числа равны, НОД найден
return n1;
int d = n1 - n2; // Находим разность чисел
if (d < 0) // если разность отрицательная,
{
d = -d; // меняем знак
div = NOD(n1, d); // вызываем функцию NOD() для двух наименьших чисел
}
else // если разность n1-n2 положительная
{
div = NOD(n2, d); // вызываем функцию NOD() для двух наименьших чисел
}
return div;
}
int main()
{
int n1, n2;
cout << "n1="; cin >> n1;
cout << "n2="; cin >> n2;
cout << NOD(n1, n2);
cin.get(); cin.get();
return 0;
}
Не мое, но очень интересное решение))
2
3
4
5
6
7
8
9
10
11
12
using namespace std;
int gcd (int a, int b) {
return b ? gcd (b, a % b) : a;
}
int main()
{
cout << gcd(10,5);
return 0;
}