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

Например, НОД чисел 12 и 18 равен 6, потому что 6 — это самое большое число, на которое делятся оба числа без остатка. 4

Для нахождения НОД можно использовать два основных способа: 3

1. Разложение на множители. 3 Нужно разложить выбранные числа на множители, проанализировать полученные в итоге множители и найти общие. 3 В конце алгоритма необходимо перемножить их. 3
2. Алгоритм Евклида. 34 Метод основан на последовательном делении. 3 Суть в том, что если меньше из чисел — делитель большего, то именно оно и станет их НОД. 3