หาตัวคูณร่วมน้อย (LCM) ของสองจำนวน

บทนำ

ในคณิตศาสตร์ ตัวคูณร่วมน้อย (Least Common Multiple - LCM) คือจำนวนเต็มที่น้อยที่สุดที่หารด้วยทั้งสองจำนวนลงตัว

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

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

Input: สองจำนวน: 6 และ 9
Output: LCM คือ: 18

อัลกอริทึม

LCMofTwo(a, b)
Input: สองจำนวน a และ b โดยพิจารณา a > b
Output: LCM ของ a และ b

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

ตัวอย่างโค้ด (C++)

#include <iostream>
using namespace std;

int findLCM(int a, int b) {
    // สมมติ a มากกว่า b
    int lcm = a, i = 2;
    while (lcm % b != 0) {
        // พยายามหาจำนวนที่เป็นพหุคูณของ b
        lcm = a * i;
        i++;
    }
    return lcm;  // LCM ของ a และ b
}

int lcmOfTwo(int a, int b) {
    int lcm;
    if (a > b)  // เพื่อส่งอาร์กิวเมนต์ตัวแรกให้มากกว่าตัวที่สอง
        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