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

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

Обозначения

Введём обозначения:

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

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

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

Алгоритм НОД

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

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

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

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

• алгоритм метода математической индукции;
• алгоритмы в арифметике;
• алгоритмы перевода чисел;
• комбинаторные алгоритмы;
• алгоритм сортировки;
• алгоритм определения мест;
• логистические алгоритмы;
• алгоритмы решения транспортных задач;
• алгоритмы численных методов;
• алгоритмы построенные с помощью машины Поста;
• алгоритмы построенные с помощью машины Тьюринга;
• алгоритм синтеза автомата Мили;
• алгоритм синтеза автомата Мура.

Ссылки

• Участник:Logic-samara