Чтобы найти делители числа с помощью алгоритма Евклида, нужно последовательно делить большее число на меньшее, потом меньшего на остаток от предыдущего деления и так далее до тех пор, пока одно число не поделится на другое. 2 Последний отличный от нуля остаток и будет искомым наибольшим делителем. 2

Последовательность шагов алгоритма: 3

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

Алгоритм Евклида тем эффективнее, чем больше числа, НОД которых следует найти. 3