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

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

PLANETCALC, Наибольший общий делитель (НОД) и наименьшее общее кратное (НОК) нескольких чисел

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

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

НОД и НОК нескольких чисел

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

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

Предположим, что у нас есть разложение чисел a и b на простые множители:

a = p^{\alpha_1}_1p^{\alpha_2}_2...p^{\alpha_n}_n \\ b = p^{\beta_1}_1p^{\beta_2}_2...p^{\beta_m}_m

Тогда НОД можно найти как произведение всех имеющихся простых множителей, взятых с минимальной степенью

p^{min(\alpha_1, \beta_1)}_1p^{min(\alpha_2, \beta_2)}_2...p^{min(\alpha_n, \beta_n)}_np^{min(\alpha_m, \beta_m)}_m

А НОК - как произведение всех имеющихся простых множителей, взятых с максимальной степенью.

p^{max(\alpha_1, \beta_1)}_1p^{max(\alpha_2, \beta_2)}_2...p^{max(\alpha_n, \beta_n)}_np^{max(\alpha_m, \beta_m)}_m

В случае отсутствия множителя в каком либо из чисел, считается что он взят с нулевой степенью.

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

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

Комментарии