🐍 Алгоритм Евклида: самый известный способ найти НОД

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

➡️ Как работает

Берем два числа: a и b.

Пока b ≠ 0:

Присваиваем a = b,

Присваиваем b = a % b (остаток от деления).

Когда b станет 0, в a будет НОД.

Пример на Python:
def gcd(a, b):
while b != 0:
a, b = b, a % b
return a

print(gcd(48, 18)) # Выведет: 6

➡️ Почему важно знать

🔵 Часто используется в криптографии (например, RSA).

🔵 Помогает при работе с дробями, оптимизацией циклов и проверкой взаимной простоты чисел.

🔵 Чтобы знать об алгоритмах все, забирайте наш курс «Алгоритмы и структуры данных»

Proglib Academy #буст