Способы вычисления

Эффективными способами вычисления НОД двух чисел являются алгоритм Евклида и бинарный алгоритм.

Кроме того, значение НОД(m, n) можно легко вычислить, если известно каноническое разложение чисел m, n на простые множители:

где — различные простые числа, а и — неотрицательные целые числа (они могут быть нулями, если соответствующее простое отсутствует в разложении). Тогда НОД(m, n) и НОК(m, n) выражаются формулами:

Если чисел более двух: , их НОД находится по следующему алгоритму:

………

— это и есть искомый НОД.