Наибольший общий делитель

Материал из ALL
Версия от 10:58, 16 января 2024; Logic-samara (обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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

Обозначения

a – первое натуральное число;

b – второе натуральное число;

n – наибольший общий делитель чисел a и b, обозначается НОД(a,b).

Алгоритм НОД

Входные данные: a; b.

НОД01.JPG

Выходные данные: n.

  • Заметим, что НОД(a,b)=ab/НОК(a,b)

Другие алгоритмы:

Шаблон:Список ААлг

Ссылки