Как найти наибольший общий делитель двух чисел?

Чтобы найти наибольший общий делитель (НОД) двух чисел, можно использовать алгоритм Евклида:

1. Начинаем с двух чисел, назовем их a и b.
2. Проверяем, не равно ли b нулю:
   • Если b равно 0, то НОД равен a.
3. Если b не равно 0, обновляем значения:
   • Присваиваем a значение b, а b — остаток от деления a на b.
4. Повторяем шаги 2 и 3, пока b не станет равным 0.
5. Когда b станет 0, a будет содержать НОД.

Примеры:

• Для чисел 5 и 3:

  • Начинаем с a = 5, b = 3.
  • Остаток от деления 5 на 3 равен 2 → обновляем a = 3, b = 2.
  • Остаток от деления 3 на 2 равен 1 → обновляем a = 2, b = 1.
  • Остаток от деления 2 на 1 равен 0 → обновляем a = 1, b = 0.
  • НОД(5, 3) = 1.

• Для чисел 3 и 15:

  • Начинаем с a = 3, b = 15.
  • Остаток от деления 3 на 15 равен 3 → обновляем a = 15, b = 3.
  • Остаток от деления 15 на 3 равен 0 → обновляем a = 3, b = 0.
  • НОД(3, 15) = 3.