Наибольший общий делитель
Перейти к навигации
Перейти к поиску
Наибольший общий делитель (НОД) — это наибольшее натуральное число (множитель) для заданных натуральных чисел, которому кратны эти числа.
Обозначения[править]
a — первое натуральное число;
b — второе натуральное число;
n — наибольший общий делитель чисел a и b, обозначается НОД(a, b).
Алгоритм НОД[править]
Входные данные: a; b.
- c = a; d = b
- Если c > d, то c = c − d
- Если c < d, то d = d − c
- Если c > d, то идти к 2
- n = c
Выходные данные: n.
- Заметим, что НОД(a, b) = ab/НОК(a, b)