โปรแกรม C++ หาตัวคูณร่วมน้อยที่สุด (LCM)

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

ตัวอย่าง: สมมติมีตัวเลข 15 และ 9

15 = 5 × 3
9 = 3 × 3

ดังนั้น LCM ของ 15 และ 9 คือ 45

โปรแกรมหา LCM ของตัวเลขสองจำนวนมีดังนี้:

วิธีที่ 1: ใช้ลูป while

#include <iostream>
using namespace std;

int main() {
    int a = 7, b = 5, lcm;
    if(a > b)
        lcm = a;
    else
        lcm = b;
    while(1) {
        if(lcm % a == 0 && lcm % b == 0) {
            cout << "The LCM of " << a << " and " << b << " is " << lcm;
            break;
        }
        lcm++;
    }
    return 0;
}

ผลลัพธ์

The LCM of 7 and 5 is 35

ในโปรแกรมนี้ ตัวแปร lcm จะถูกกำหนดให้เป็นค่าที่มากกว่าระหว่างสองจำนวน จากนั้นลูป while จะทำงานเพื่อตรวจสอบว่า lcm หารด้วย a และ b ลงตัวหรือไม่ หากใช่ จะแสดงผลและออกจากลูป หากไม่ ก็จะเพิ่มค่า lcm ขึ้นทีละ 1 จนกว่าจะเจอ

วิธีที่ 2: ใช้สูตร LCM และ GCD

สูตรความสัมพันธ์ระหว่าง LCM และ GCD (ตัวหารร่วมมาก) คือ:

a × b = GCD × LCM

โปรแกรมหา LCM โดยใช้สูตรนี้:

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

int main() {
    int a = 7, b = 5;
    cout << "LCM of " << a << " and " << b << " is " << (a * b) / gcd(a, b);
    return 0;
}

ผลลัพธ์

LCM of 7 and 5 is 35

ในวิธีนี้ จะหา GCD ก่อนโดยใช้ฟังก์ชันแบบเรียกซ้ำ (recursive) จากนั้นคำนวณ LCM จากสูตร (a * b) / gcd(a, b)