Как найти нод для нескольких чисел

Как найти НОД

• Нахождение путём разложения на множители
• Алгоритм Евклида

Рассмотрим два способа нахождения наибольшего общего делителя.

Нахождение путём разложения на множители

Первый способ заключается в нахождении наибольшего общего делителя путём разложения данных чисел на простые множители.

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

Алгоритм Евклида

Второй способ (иначе его называют способом Евклида) заключается в нахождении НОД путём последовательного деления.

Сначала мы рассмотрим этот способ в применении только к двум данным числам, а затем разберёмся в том, как его применять к трём и более числам.

Если большее из двух данных чисел делится на меньшее, то число, которое меньше и будет их наибольшим общим делителем.

В остальных случаях, чтобы найти наибольший общий делитель двух чисел используется следующий порядок действий:

1. Из двух данных чисел большее число делят на меньшее.
2. Затем, меньшее число делят на остаток, получившийся от деления большего числа на меньшее.
3. Далее, первый остаток делят на второй остаток, который получился от деления меньшего числа на первый остаток.
4. Второй остаток делят на третий, который получился от деления первого остатка на второй и т. д.
5. Таким образом деление продолжается до тех пор, пока в остатке не получится нуль. Последний делитель как раз и будет наибольшим общим делителем.

Чтобы найти наибольший общий делитель трёх и более данных чисел, используем следующий порядок действий:

1. Сперва находим наибольший общий делитель любых двух чисел из нескольких данных.
2. Затем находим НОД найденного делителя и какого-нибудь третьего данного числа.
3. Затем находим НОД последнего найденного делителя и четвёртого данного числа и так далее.

Онлайн калькулятор НОД и НОК двух чисел

Наибольший общий делитель (НОД)

Если натуральное число a делится на натуральное число bb, то bb называют делителем числа aa, а число aa называют кратным числа bb. aa и bb являются натуральными числами. Число gg называют общим делителем и для aa и для bb. Множество общих делителей чисел aa и bb конечно, так как ни один из этих делителей не может быть больше, чем aa. Значит, среди этих делителей есть наибольший, который называют наибольшим общим делителем чисел aa и bb и для его обозначения используют записи: НОД (a;b)(a;b) или D(a;b)(a;b)

Пример
Наибольший общий делитель (НОД) чисел 1818 и 2424 — это 66.

Как найти наибольший общий делитель (НОД)

Существует несколько способов нахождения наибольшего общего делителя (НОД) двух или более целых чисел:

• Алгоритм Евклида: НОД(a,b)=(a, b) = НОД (b,a(b, a mod b)b), где «mod» — это операция взятия остатка от деления большего числа на меньшее. Этот алгоритм можно продолжать до тех пор, пока одно из чисел не станет равно нулю. В этом случае НОД равен ненулевому числу.

Пример
НОД(18,24)=НОД(24,18)=НОД(18,6)=НОД(6,0)=6НОД(18, 24) = НОД(24, 18) = НОД(18, 6) = НОД(6, 0) = 6

• Разложение на простые множители: Найти все простые множители каждого из чисел и их степени. НОД будет равен произведению всех общих простых множителей в минимальной степени.

Пример
НОД(60,84)=22⋅31=12(60, 84) = 2^{2} cdot 3^{1} = 12, так как общие простые множители −2- 2 и 33, их минимальные степени −2- 2 и 11 соответственно.

• Таблица делителей: Составить таблицы всех делителей каждого числа и найти наибольшее общее число, которое является делителем обоих чисел. Этот метод не рекомендуется для больших чисел, так как он требует много времени и усилий.

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

Общими кратными чисел называются числа которые делятся на исходные без остатка. Например для чисел 2525 и 5050 общими кратными будут числа 50,100,150,20050,100,150,200 и т.д Наименьшее из общих кратных будет называться НОК и обозначается НОК(a;b)(a;b) или K(a;b).(a;b).

Пример
Наименьшее общее кратное чисел 88 и 1212 – это 2424. Т.е. НОК (8,12)=24(8, 12) = 24.

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

Чтобы найти НОК двух чисел, необходимо:

1. Разложить числа на простые множители;
2. Выписать множители, входящие в состав первого числа и добавить к ним множители, которые входят в состав второго и не ходят в состав первого;
3. Найти произведение чисел, найденных на шаге 2. Полученное число и будет искомым наименьшим общим кратным.

Пример
Рассмотрим два числа: 88 и 1212. Найдем их НОКНОК:

• Разложим 88 и 1212 на простые множители: 8=23,12=22⋅38 = 2^3, 12 = 2^2 cdot 3.
• Выпишем все простые множители: 23⋅32^3 cdot 3.
• Для каждого простого множителя выберем наибольшую кратность: 232^3 и 33.
• Умножим выбранные простые множители между собой: 23⋅3=242^3 cdot 3 = 24.

Таким образом, НОК чисел 88 и 1212 равен 2424.

Свойства НОД и НОК

• Любое общее кратное чисел aa и bb делится на K(a;b)(a;b);
• Если a⋮bavdots b , то К(a;b)=a(a;b)=a;
• Если К(a;b)=k(a;b)=k и mm-натуральное число, то К(am;bm)=km(am;bm)=km. Если dd-общий делитель для aa и bb,то К(ad;bdfrac{a}{d};frac{b}{d})= kd frac{k}{d}
• Если a⋮cavdots c и b⋮cbvdots c ,то abcfrac{ab}{c} — общее кратное чисел aa и bb;
• Для любых натуральных чисел aa и bb выполняется равенство D(a;b)⋅К(a;b)=abD(a;b)cdot К(a;b)=ab;
• Любой общий делитель чисел aa и bb является делителем числа D(a;b)D(a;b).

Вычисление НОД — ошибка, которой не замечают

Что такое НОД, все знают еще со школы. Для тех, кто подзабыл, напомню: НОД — наибольший общий делитель, делящий два целых числа без остатка. Например, НОД чисел 100 и 45 равен 5, а НОД чисел 17 и 7 равен 1. Существует несколько различных алгоритмов поиска этого числа. Однако, несмотря на то, что это достаточно простые алгоритмы, часто совершают одну маленькую, но очень существенную ошибку.

Алгоритмы вычисления НОД

Я рассмотрю 5 алгоритмов вычисления НОД:

public static int gcd_1(int a, int b) {
	if (b == 0)
		return a;
	return gcd_1(b, a % b);
}

public static int gcd_2(int a, int b) {
	int t;
	while (b != 0) {
		t = b;
		b = a % b;
		a = t;
	}
	return a;
}

public static int gcd_3(int a, int b) {
	while (a != b) {
		if (a > b) {
			a = a - b;
		} else {
			b = b - a;
		}
	}
	return a;
}

public static int gcd_4(int a, int b) {
	if (a == b)
		return a;
	if (a == 0)
		return b;
	if (b == 0)
			return a;
	if ((~a & 1) != 0) {
		if ((b & 1) != 0)
			return gcd_4(a >> 1, b);
		else
			return gcd_4(a >> 1, b >> 1) << 1;
	}
	if ((~b & 1) != 0)
		return gcd_4(a, b >> 1);
	if (a > b)
		return gcd_4((a - b) >> 1, b);
	return gcd_4((b - a) >> 1, a);
}

public static int gcd_5(int a, int b) {
	int shift;
	if (a == 0)
		return b;
	if (b == 0)
		return a;
	for (shift = 0; ((a | b) & 1) == 0; ++shift) {
		a >>= 1;
		b >>= 1;
	}
	while ((a & 1) == 0)
		a >>= 1;
		do {
		while ((b & 1) == 0)
			b >>= 1;
		if (a > b) {
			int t = b;
			b = a;
			a = t;
		}
		b = b - a;
	} while (b != 0);
	return a << shift;
}

Естественно, чаще всего пишут первый вариант — он легко запоминается, быстро пишется и достаточно быстро работает.

Претесты

Реализации корректно работают на таких тестах:

gcd(1, 10) = 1
gcd(5, 10) = 5
gcd(24, 24) = 24
gcd(0, 0) = 0
gcd(5,10) = 5

Естественно, они будут работать и на подобных тестах, где в качестве аргументов выступают целые неотрицательные числа. Но что, если…

Первые тесты с подвохом

… если заменить одно из чисел нулем? Например так:

gcd(5, 0) = 5
gcd(0, 15) = 15

Классический алгоритм Евклида (№3) уже попадает в бесконечный цикл.

Копаем глубже

Согласно определению, НОД может быть определен для любых двух целых чисел. Так почему бы не попробовать тесты, где одно из чисел — отрицательное:

gcd(-5,10) = ?

Все становится еще интереснее. Первые две реализации выдают в качестве ответа -5. Третий алгоритм снова попадает в бесконечный цикл. Вместе с ним в бесконечном цикле оказывается пятый алгоритм. Четвертый падает по StackOverFlow — скорее всего тоже попадает в бесконечный цикл.
Но ведь ответ -5 — неправильный. По определению НОД — наибольший общий делитель. А таковым является число 5. Ведь и первое, и второе число

делятся без остатка

на 5. Значит и первые две реализации не дают верный ответ.

Почему решения №№3-5 попадают в бесконечный цикл?

Алгоритм Евклида попадает в цикл из-за бесконечного увеличения аргументов, если один из них отрицательный. Действительно, если посмотреть на эти строки, то можно заметить, что при отрицательном a (или b) операция вычитания заменяется сложением.

if (a > b) {
	a = a - b;
} else {
	b = b - a;
}

Аналогичное происходит в четвертом и пятом алгоритме:

if (a > b)
	return gcd_4((a - b) >> 1, b);
return gcd_4((b - a) >> 1, a);

if (a > b) {
	int t = b;
	b = a;
	a = t;
}
b = b - a;

В ситуации, когда a или b равны 0, то происходит бесконечное вычитание нуля, которое никаким образом не меняет значения аргументов.

Так что же не так?

Все эти алгоритмы корректны для входных данных, когда оба числа a и b — целые неотрицательные числа. Но вспомним еще раз — НОД существует для любых двух целых чисел.

Что же делать?

В качестве аргументов в функцию можно передавать абсолютное значение чисел, тогда ответ будет корректен:

int ans = gcd(Math.abs(a), Math.abs(b));

Второй способ решения задачи — возвращать абсолютное значение ответа:

public static int gcd(int a, int b) {
	if (b == 0)
		return Math.abs(a);
	return gcd(b, a % b);
}

Второй вариант гораздо предпочтительнее: будет производиться меньше лишних вычислений, чем в первом варианте.

Итоги

Мы рассмотрели пять различных вариантов вычисления наибольшего общего делителя. Для каждого из них мы указали входные данные, на которых ответ существует, но решение «падает», а также способ решения проблемы.
Такие небольшие ошибки чаще всего допускаются по причине того, что не замечают «скользкие» места решения какой-то задачи. Часть из них отлавливается в процессе тестирования, а часть остается незамеченной.
В ситуации с вычислением НОД

почти

все реализации приведены с ошибкой. В Сети я нашел лишь парочку корректно работающих решений, остальные идентичны тем, что приведены в начале поста.

Используемая литература, источники, реализации:

• Binary GCD algorithm — Wikipedia
• Euclidean algorithm — Wikipedia
• Алгоритм Евклида — e-maxx
• Binary GCD — Dictionary of Algorithms and Data Structures
• Кормен — Алгоритмы — построение и анализ

Наибольшим общим делителем (НОД) двух целых чисел называется наибольший из их общих делителей. К примеру для чисел 12 и 8, наибольшим общим делителем будет 4.

Как найти НОД?

Способов найти НОД несколько. Мы рассмотрим один из часто используемых в математике — это нахождение НОД при помощи разложения чисел на простые множители. В общем случае алгоритм будет выглядеть следующим образом:

1. разложить оба числа на простые множители (подробнее о разложении чисел на простые множители смотрите тут);
2. выбрать одинаковые множители, входящие в оба разложения;
3. найти их произведение.

Примеры нахождения наибольшего общего делителя

Рассмотрим приведенный алгоритм на конкретных примерах:

Пример 1: найти НОД 12 и 8

2. Выбираем одинаковые множители, которые есть в обоих разложениях. Это: 2 и 2

3. Перемножаем эти множители и получаем: 2 · 2 = 4

Ответ: НОД (8; 12) = 2 · 2 = 4.

Пример 2: найти НОД 75 и 150

Этот пример, как и предыдущий с легкостью можно высчитать в уме и вывести ответ 75, но для лучшего понимания работы алгоритма, проделаем все шаги:

2. Выбираем одинаковые множители, которые есть в обоих разложениях. Это: 3, 5 и 5

3. Перемножаем эти множители и получаем: 3 · 5 · 5 = 75

Ответ: НОД (75; 150) = 3 · 5 · 5 = 75.

Частный случай или взаимно простые числа

Нередко встречаются ситуации, когда оба числа взаимно простые, т.е. общий делитель равен единице. В этом случае, алгоритм будет выглядеть следующим образом:

Пример 3: найти НОД 9 и 5

Видим, что одинаковых множителей нет, а значит, что это частный случай (взаимно простые числа). Общий делитель — единица.

В данной статье мы рассмотрим определение наибольшего общего делителя, научимся его находить для двух или нескольких чисел, а также разберем практические примеры для закрепления изложенного материала.

Определение наибольшего общего делителя

Делитель натурального числа a – это такое натуральное число b, которое делит a нацело (без остатка). Обозначается буквой Д. Например Д(6) означает “делитель числа 6”.

Если у числа больше двух делителей, его называют составным.

Примеры делителей:

• Число 12 имеет следующие делители: 1, 2, 3, 4, 6.
• Число 15 имеет следующие делители: 1, 3, 5.

В отличие от кратных, количество делителей числа ограничено.

Общий делитель двух натуральных чисел – это такое число, на которое оба этих числа делятся без остатка.

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

Например, НОД (12, 24) – это наибольший общий делитель чисел 12 и 24.

Нахождение НОД

Чтобы найти наибольший общий делитель, можно применить один из способов ниже.

Для двух (или небольших) чисел

1. Записываем в ряд все делители для каждого числа (по возрастанию).
2. Находим наибольшее значение, встречающееся в обоих рядах. Это и есть НОД.

Пример
Найдем наибольший делитель чисел 18 и 30.

Решение
Д(18): 1, 2, 3, 6, 9.
Д(30): 1, 2, 3, 5, 6, 10, 15.

Таким образом, НОД (18, 30) = 6.

Для нескольких (или больших) чисел

Этот метод обычно применяется, если приходится иметь дело с большим числами, или нужно найти НОД для нескольких чисел.

1. Для начала раскладываем числа на простые множители – простые числа, которые делят число без остатка.
2. Отмечаем одинаковые простые множители, встречающиеся в обоих раскладках.
3. Произведение найденных простых множителей и есть НОД.

Пример
Найдем НОД (16, 24, 40).

Решение
Разложим эти числа на простые множители.

Для всех трех чисел одинаковыми являются три множителя – это три двойки.

Следовательно, НОД (16, 24, 40) = 2 ⋅ 2 ⋅ 2 = 8.