محاسبه ب.م.م و ک.م.م در پایتون

طبق الگوریتم اقلیدس، ب.م.م دو عدد با ب.م.م عدد دوم و باقی‌ماندهٔ تقسیم آن دو برابر است. این جایگزینی را تا وقتی تکرار کنید که باقی‌مانده صفر شود.

a = int(input())
b = int(input())

x, y = a, b
while y != 0:
    x, y = y, x % y

gcd = x
lcm = a * b // gcd

print(gcd)
print(lcm)

این جواب چطور کار می‌کند؟

در هر دور حلقه، x, y = y, x % y دو عدد را با عدد دوم و باقی‌ماندهٔ تقسیم عوض می‌کند. عددها سریع کوچک می‌شوند و وقتی y صفر شد، x همان ب.م.م است. برای ۱۲ و ۱۸ این مسیر به ۱۸ و ۱۲، بعد به ۱۲ و ۶ و در آخر به ۶ و ۰ می‌رسد.

حلقه روی x و y کار می‌کند تا a و b دست‌نخورده بمانند، چون برای حساب ک.م.م به خود دو عدد هم نیاز است.

حاصل‌ضرب دو عدد همیشه با حاصل‌ضرب ب.م.م و ک.م.م آن‌ها برابر است. پس ک.م.م برابر a * b // gcd است. علامت // نتیجه را عدد صحیح نگه می‌دارد و خروجی 36 است، نه 36.0.

راه دوم: توابع آمادهٔ math

import math

a = int(input())
b = int(input())

print(math.gcd(a, b))
print(math.lcm(a, b))

math.gcd از پایتون ۳٫۵ و math.lcm از پایتون ۳٫۹ در کتابخانهٔ استاندارد هستند. در برنامهٔ واقعی همین‌ها را به کار ببرید؛ نوشتن الگوریتم اقلیدس با دست برای فهمیدن روش و حل تمرین است.