Любая сложная задача всегда может быть разбита на несколько простых задач. Те в свою очередь могут быть разбиты на ещё1 более мелкие задачи. В олимпиадных задачах по программированию очень часто требуется найти НОД(наибольший общий делитель) или НОК(наименьшее общее кратное) двух или более чисел. Это может быть задача по фасовке предметам по ящикам (целочисленное деление) или формирование людей в бригады. Короче там где нужно искать целые числа после деления. Пример двух чисел 6 и 15. Очевидно, что НОД (наибольшим общим делителем) будет число 3...

Здравствуйте, дорогие читатели! Сегодня мы разберем элементарный способ нахождения НОД. Чаще всего, наибольший общий делитель находят с помощью разложения на простые множители. Так как этот способ самый привычный для нас, то его мы сегодня трогать не будем. На самом деле, существуют два способа вычисления НОД с помощью алгоритма Евклида. Но, Евклид сформулировал одно единственное правило, с помощью которого находится наибольший общий делитель. Хотя, если уж совсем честно, то Евклид и вовсе этого правила не формулировал...

Введение В данной статье рассмотрим три способа найти наибольший общий делитель (НОД) в Python. Использование функции math.gcd() Для нахождения НОД мы можем воспользоваться готовой функцией gcd() из встроенного модуля math. Разбираем модуль math в Python Синтаксис функции math.gcd(): import math math.gcd(int1, int2) # Возвращает наибольший общий делитель двух целых чисел int1 и int2 Примеры: import math print(math.gcd(3, 6)) # Вывод: 3 print(math.gcd(6, 12)) # Вывод: 6 print(math.gcd(12, 36)) # Вывод: 12 print(math...