نفر قبلی جواب درستی داد اما صرفا برای توضیح بیشتر:
کد برنامه رو که این طوری هم میشه نوشت:
int gcd(int a, int b)
{
if(b==0) return a;
return gcd(b, a%b);
}
int lcm(int a, int b)
{
return a*b/gcd(a, b);
}
این الگوریتم، در بین سایر الگوریتم های محاسبه ی ب م م از کمترین زمان ممکن استفاده میکنه و از مرتبه log n هستش یعنی اگر ورودی شما عدد n باشد، این الگوریتم به مقدار " log n در مبنای 2 " دستور را توسط cpu انجام میدهد.
روش کارش همون روش نردبانی هست که توی اول راهنمایی یاد گرفتیم.
لازم به ذکره که تابع gcd اگر b!=0 باشه به صورت خودکار دستور دوم را انجام میدهد. چون return در توابع مثل break در حلقه است.
نکته ی دیگه این که اگر ورودی های تابع ب.م.م به شکلی باشد که عدد اول کوچکتر از عدد دوم باشد، یعنی a<b :
gcd (a, b) = gcd (b, a%b) = gcd (b, a)
یعنی اگر a<b باشد، خود تابع به صورت اتوماتیک، جای آن دو را عوض میکند و نیازی نیست که مستقیما از دستور if استفاده کنیم.