![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Эффективными способами вычисления НОД двух чисел являются алгоритм Евклида и бинарный алгоритм.
Кроме того, значение НОД(m, n) можно легко вычислить, если известно каноническое разложение чисел m, n на простые множители:
где — различные простые числа, а
и
— неотрицательные целые числа (они могут быть нулями, если соответствующее простое отсутствует в разложении). Тогда НОД(m, n) и НОК(m, n) выражаются формулами:
Если чисел более двух: , их НОД находится по следующему алгоритму:
………
— это и есть искомый НОД.
Дата публикования: 2015-04-08; Прочитано: 237 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!