ค้นหา LCM ของตัวเลขสองตัว

ในทางคณิตศาสตร์ ตัวคูณร่วมน้อย (LCM) เป็นจำนวนเต็มที่น้อยที่สุดที่เป็นไปได้ ซึ่งหารด้วยตัวเลขทั้งสองลงตัว

LCM สามารถคำนวณได้หลายวิธี เช่น การแยกตัวประกอบ ฯลฯ แต่ในอัลกอริธึมนี้ เราได้คูณจำนวนที่มากกว่าด้วย 1, 2, 3…. n จนกว่าเราจะพบตัวเลขที่หารด้วยจำนวนที่สองลงตัว

อินพุตและเอาต์พุต

Input:
Two numbers: 6 and 9
Output:
The LCM is: 18

อัลกอริทึม

LCMofTwo(a, b)

ป้อนข้อมูล: ตัวเลขสองตัว a และ b ถือเป็น a> b.

ผลลัพธ์: LCM ของ a และ b.

Begin
   lcm := a
   i := 2
   while lcm mod b ≠ 0, do
      lcm := a * i
      i := i + 1
   done

   return lcm
End

ตัวอย่าง

#include<iostream>
using namespace std;

int findLCM(int a, int b) {    //assume a is greater than b
   int lcm = a, i = 2;

   while(lcm % b != 0) {    //try to find number which is multiple of b
      lcm = a*i;
      i++;
   }
   return lcm;    //the lcm of a and b
}

int lcmOfTwo(int a, int b) {
   int lcm;
   if(a>b)    //to send as first argument is greater than second
      lcm = findLCM(a,b);
   else
      lcm = findLCM(b,a);
   return lcm;
}

int main() {
   int a, b;
   cout << "Enter Two numbers to find LCM: "; cin >> a >> b;
   cout << "The LCM is: " << lcmOfTwo(a,b);
}

ผลลัพธ์

Enter Two numbers to find LCM: 6 9
The LCM is: 18