Как найти наибольший общий делитель чисел

Нод и нок чисел с решением | наибольший общий делитель и наименьшее общее кратное нескольких чисел

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

Калькулятор для нахождения НОД и НОК

Найти НОД и НОК

Найдено НОД и НОК: 11342

Как пользоваться калькулятором

• Введите числа в поле для ввода
• В случае ввода некорректных символов поле для ввода будет подсвечено красным
• нажмите кнопку “Найти НОД и НОК”

Как вводить числа

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

Наибольший общий делитель нескольких чисел – это наибольшее натуральное целое число, на которое все исходные числа делятся без остатка. Наибольший общий делитель сокращённо записывается как НОД.
Наименьшее общее кратное нескольких чисел – это наименьшее число, которое делится на каждое из исходных чисел без остатка. Наименьшее общее кратное сокращённо записывается как НОК.

Как проверить, что число делится на другое число без остатка?

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

Некоторые признаки делимости чисел

1. Признак делимости числа на 2Чтобы определить, делится ли число на два (является ли оно чётным), достаточно посмотреть на последнююю цифру этого числа: если она равна 0, 2, 4, 6 или 8, то число чётно, а значит делится на 2.

Пример: определить, делится ли на 2 число 34938.

Решение: смотрим на последнюю цифру: 8 – значит число делится на два.

2. Признак делимости числа на 3Число делится на 3 тогда, когда сумма его цифр делится на три. Таким образом, чтобы определить, делится ли число на 3, нужно посчитать сумму цифр и проверить, делится ли она на 3. Даже если сумма цифр получилась очень большой, можно повторить этот же процесс вновь.

Пример: определить, делится ли число 34938 на 3.

Решение: считаем сумму цифр: 3+4+9+3+8 = 27. 27 делится на 3, а значит и число делится на три.

3. Признак делимости числа на 5Число делится на 5 тогда, когда его последняя цифра равна нулю или пяти.

Пример: определить, делится ли число 34938 на 5.

Решение: смотрим на последнюю цифру: 8 – значит число НЕ делится на пять.

4. Признак делимости числа на 9Этот признак очень похож на признак делимости на тройку: число делится на 9 тогда, когда сумма его цифр делится на 9.

Пример: определить, делится ли число 34938 на 9.

Решение: считаем сумму цифр: 3+4+9+3+8 = 27. 27 делится на 9, а значит и число делится на девять.

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

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

Рассмотрим этот способ на примере нахождения НОД(28, 36):

1. Раскладываем оба числа на множители: 28 = 1·2·2·7, 36 = 1·2·2·3·3
2. Находим общие множители, то есть те, которые есть у обоих чисел: 1, 2 и 2.
3. Вычисляем произведение этих множителей: 1·2·2 = 4 – это и есть наибольший общий делитель чисел 28 и 36.

Как найти НОК двух чисел

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

Для вычисления НОК нужно вычислить произведение исходных чисел и затем разделить его на предварительно найденный НОД. Найдём НОК для тех же чисел 28 и 36:

1. Находим произведение чисел 28 и 36: 28·36 = 1008
2. НОД(28, 36), как уже известно, равен 4
3. НОК(28, 36) = 1008 / 4 = 252.

Нахождение НОД и НОК для нескольких чисел

Наибольший общий делитель можно находить и для нескольких чисел, а не только для двух. Для этого числа, подлежащие поиску наибольшего общего делителя, раскладывают на простые множители, затем находят произведение общих простых множителей этих чисел. Также для нахождение НОД нескольких чисел можно воспользоваться следующим соотношением: НОД(a, b, c) = НОД(НОД(a, b), c).

Аналогичное соотношение действует и для наименьшего общего кратного чисел: НОК(a, b, c) = НОК(НОК(a, b), c)

Пример: найти НОД и НОК для чисел 12, 32 и 36.

1. Cперва разложим числа на множители: 12 = 1·2·2·3, 32 = 1·2·2·2·2·2, 36 = 1·2·2·3·3.
2. Найдём обшие множители: 1, 2 и 2.
3. Их произведение даст НОД: 1·2·2 = 4
4. Найдём теперь НОК: для этого найдём сначала НОК(12, 32): 12·32 / 4 = 96.
5. Чтобы найти НОК всех трёх чисел, нужно найти НОД(96, 36): 96 = 1·2·2·2·2·2·3, 36 = 1·2·2·3·3, НОД = 1·2·2·3 = 12.
6. НОК(12, 32, 36) = 96·36 / 12 = 288.

Источник: https://programforyou.ru/calculators/nod-i-nok-chisel

8 способов нахождения наибольшего общего делителя

Эта статья появилась на свет совершенно неожиданно. Мне на глаза случайно попался код вычисления НОД на C#.

С первого взгляда мне даже всё понравилось: простенько, лаконичненько и без лишнего выпендрёжа. Однако чем дольше я рассматривал этот код, тем больше возникало сомнений в его эффективности. Я решил сделать маленькое исследование.

В адаптации на C++ код выглядел примерно так:

#include using namespace std; int main() { int a, b; cin >> a >> b; for (int i = a; i > 0; i–) { if (a % i == 0 && b % i == 0) { cout b ? b : a;} long gcd02(long a, long b) { long nod = 1L; for (long i = min(a, b); i > 0; i–) { if (a % i == 0 && b % i == 0) { nod = i; break; } } return nod;}

Просто добавляем простейшую функцию для вычисления минимального числа для пары чисел и инициализируем переменную цикла меньшим из двух чисел. В половине случаев такая оптимизация работать не будет (когда первый аргумент и так меньше второго); зато в другой половине случаев выигрыш по времени может быть весьма значительным.

03 алгоритм с разложением на делители

Но второй вариант так и остался алгоритмом с последовательным перебором. Что можно попробовать ещё?

Из школьного курса математики известно, что НОД можно найти из разложения чисел на простые множители.

a = m1 * m2 * m3 * … * mNгде m – простые числа

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

24 = (2) * 2 * 2 * (3)54 = (2) * (3) * 3 * 3 общие множители выделены скобками НОД(24, 54) = 2 * 3 = 6

Реализуем эту идею:

long gcd03(long a, long b) { long nod = 1L; if (a > b) { long tmp = a; a = b; b = tmp; } while (a > 1L && b > 1L) { for (long i = 2; i b) { long tmp = a; a = b; b = tmp; } return gcd04(a, b – a);}

Считается, что рекурсивные алгоритмы менее эффективны, чем итерационные, за счёт накладных расходов на вызов функции. Для проверки делаем и итерационный вариант.

05 алгоритм Евклида (итерационный)

long gcd05(long a, long b) { while (a != b) { if (a > b) { long tmp = a; a = b; b = tmp; } b = b – a; } return a;}

Кстати, в Викиучебнике есть и другие реализации алгоритма Евклида.

06 бинарный алгоритм (рекурсивный)

Бинарный алгоритм Евклида.

1. НОД(0, n) = n; НОД(m, 0) = m; НОД(m, m) = m;
2. НОД(1, n) = 1; НОД(m, 1) = 1;
3. Если m, n чётные, то НОД(m, n) = 2*НОД(m/2, n/2);
4. Если m чётное, n нечётное, то НОД(m, n) = НОД(m/2, n);
5. Если n чётное, m нечётное, то НОД(m, n) = НОД(m, n/2);
6. Если m, n нечётные и n > m, то НОД(m, n) = НОД((n-m)/2, m);
7. Если m, n нечётные и n < m, то НОД(m, n) = НОД((m-n)/2, n);

Рекурсивная версия:

long gcd06(long a, long b) { if (a == 0L) return b; if (b == 0L) return a; if (a == b) return a; if (a == 1L || b == 1L) return 1L; if (a % 2L == 0L && b % 2L == 0L) return 2L * gcd06(a / 2L, b / 2L); if (a % 2L == 0L && b % 2L != 0L) return gcd06(a / 2L, b); if (a % 2L != 0L && b % 2L == 0L) return gcd06(a, b / 2L); if (a < b) return gcd06((b - a) / 2L, a); else return gcd06((a - b) / 2L, b);}

07 бинарный алгоритм (итерационный)

Итерационная версия:

long gcd07(long a, long b) { long nod = 1L; long tmp; if (a == 0L) return b; if (b == 0L) return a; if (a == b) return a; if (a == 1L || b == 1L) return 1L; while (a != 0 && b != 0) { if (a % 2L == 0L && b % 2L == 0L) { nod *= 2L; a /= 2L; b /= 2L; continue; } if (a % 2L == 0L && b % 2L != 0L) { a /= 2L; continue; } if (a % 2L != 0L && b % 2L == 0L) { b /= 2L; continue; } if (a > b) { tmp = a; a = b; b = tmp; } tmp = a; a = (b – a) / 2L; b = tmp; } if (a == 0) return nod * b; else return nod * a;}

Кстати, в Викиучебнике есть и другие реализации бинарного алгоритма Евклида.

08 бинарный алгоритм (итерационный) с использованием битовых операций

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

Эта версия функции по логике полностью совпадает с предыдущей, но операции деления и умножения на 2 заменены арифметическими сдвигами, а проверка на чётность – на проверку младшего бита числа.

long gcd08(long a, long b) { long nod = 1L; long tmp; if (a == 0L) return b; if (b == 0L) return a; if (a == b) return a; if (a == 1L || b == 1L) return 1L; while (a != 0 && b != 0) { if (((a & 1L) | (b & 1L)) == 0L) { nod = 1L; b >>= 1L; continue; } if (((a & 1L) == 0L) && (b & 1L)) { a >>= 1L; continue; } if ((a & 1L) && ((b & 1L) == 0L)) { b >>= 1L; continue; } if (a > b) { tmp = a; a = b; b = tmp; } tmp = a; a = (b – a) >> 1L; b = tmp; } if (a == 0) return nod * b; else return nod * a;}

Ещё немного подготовки

Итак, функции, на которые хватило времени, мозгов и фантазии написаны. Можно допиливать «испытательный стенд» и приступать к тестированию.

Как показали результаты тестовых прогонов, время работы функций сильно зависит от входных данных. Поэтому было решено генерировать случайные пары чисел.

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

В остальном алгоритм тестирования прост: для каждого набора случайных данных берётся одна из тестируемых функций и прогоняется REPEAT_TIMES раз. Время работы функции записывается в элемент массива, соответствующий этой функции. После того, как все тесты пройдены, результаты из массива делятся на количество наборов данных – получаем среднее время для набора.

#include #include #include #include using namespace std; //// здесь должны быть определения функций вычисления НОД// struct sub { long(*func)(long, long); const char * comm;}; sub arr[] = { { gcd01, “01 перебор от произвольного числа ” }, { gcd02, “02 перебор от минимального числа ” }, { gcd03, “03 с разложением на делители ” }, { gcd04, “04 алгоритм Евклида рекурсивный ” }, { gcd05, “05 алгоритм Евклида итерационный ” }, { gcd06, “06 бинарный алгоритм рекурсивный ” }, { gcd07, “07 бинарный алгоритм итерационный ” }, { gcd08, “08 бинарный алгоритм итерац. со сдвигом ” }}; const unsigned int RAND_TIMES = 500u;const unsigned long REPEAT_TIMES = 10000uL; int main() { clock_t the_time; double elapsed_time; setlocale(LC_ALL, “Russian”); long a, b, c, nod; srand((unsigned int)time(NULL)); double times[sizeof(arr) / sizeof(sub)] = { 0.0 }; for (unsigned int t = 0u; t < RAND_TIMES; t++) { c = rand() % 50 + 1; a = (rand() % 1000 + 1) * c; b = (rand() % 1000 + 1) * c; for (unsigned int alg = 0u; alg < sizeof(arr) / sizeof(sub); alg++) { the_time = clock(); for (unsigned long m = 0uL; m < REPEAT_TIMES; m++) { nod = arr[alg].func(a, b); } elapsed_time = double(clock() - the_time) / CLOCKS_PER_SEC; times[alg] += elapsed_time; } printf("%4u НОД(%7ld, %7ld) = %7ld", t + 1, a, b, nod); } printf("Среднее время для %d пар случайных чисел:", RAND_TIMES); for (unsigned int alg = 0; alg < sizeof(arr) / sizeof(sub); alg++) { printf("%s: %8.4f сек.", arr[alg].comm, times[alg] / RAND_TIMES); } return 0;}

Тестирование

Программа компилировалась под MS Visual Studio 2013 и TDM-GCC 4.8.1 в режиме 64-bit Release.

Среднее время для 500 пар случайных чисел:——————————————————-01 перебор от произвольного числа : 0.5022 сек.02 перебор от минимального числа : 0.3256 сек.03 с разложением на делители : 0.0063 сек.04 алгоритм Евклида рекурсивный : 0.0007 сек.

05 алгоритм Евклида итерационный : 0.0008 сек.06 бинарный алгоритм рекурсивный : 0.0006 сек.07 бинарный алгоритм итерационный : 0.0003 сек.08 бинарный алгоритм итерац. со сдвигом : 0.0002 сек.

Как и ожидалось, первый алгоритм катастрофически неэффективен.

Алгоритм №2 – минимальный костыль для №1 – работает почти в 2 раз быстрее.

Третий алгоритм неожиданно показал очень достойный результат: в 50 раз быстрее алгоритма №2.

Четвёртый и пятый варианты – алгоритм Евклида: рекурсивная версия, как ни странно, обогнала итерационную. По сравнению с третьим вариантом время улучшилось почти на порядок.

https://www.youtube.com/watch?v=Lkw7OMRlsLk

Бинарный алгоритм Евклида показал наилучшие результаты. Из трёх вариантов реализации рекурсивная версия – самая неторопливая. Наилучший результат у оптимизированной версии с использованием битовых операций.

Итого, самая производительная версия работает более чем в 2500 раз быстрее, чем изначальный вариант.

Примечание. Время, указанное в таблице – это время выполнения REPEAT_TIMES вызовов функции.

Выводы

Выводы достаточно банальны, но всё же:

1. Первый пришедший на ум алгоритм решения какой-то задачи часто неоптимален. Хотя и может правильно и достаточно приемлемо работать в определённых условиях.
2. Всегда надо попробовать подумать над усовершенствованием алгоритма или над альтернативным вариантом.
3. Учите математику!
4. Если есть возможность, посмотрите что сделали люди до вас. Может не стоит изобретать велосипед?
5. Оптимизируйте код.

Cranium aka Череп

Источник: https://code-live.ru/post/greatest-common-denominator-algorithms/