โปรแกรม C++ หาค่าตัวหารร่วมมาก (GCD) และตัวคูณร่วมน้อย (LCM) ของ n ตัวเลข

การหา GCD และ LCM

นี่คือโค้ดสำหรับหาค่าตัวหารร่วมมาก (GCD) และตัวคูณร่วมน้อย (LCM) ของ n ตัวเลข ตัวหารร่วมมาก (Greatest Common Divisor) ของจำนวนเต็ม 2 ตัวขึ้นไปที่ไม่ใช่ศูนย์ทั้งหมด คือจำนวนเต็มบวกที่มากที่สุดที่หารตัวเลขแต่ละตัวลงตัว GCD ยังเรียกอีกอย่างว่า ตัวหารร่วมมากที่สุด (Greatest Common Factor)

ตัวคูณร่วมน้อย (Least Common Multiple - LCM) ของตัวเลข 2 ตัว คือตัวเลขที่น้อยที่สุด (ไม่ใช่ศูนย์) ที่เป็นพหุคูณของทั้งสองตัวเลข

อัลกอริทึม

เริ่มต้น
  รับตัวเลข 2 ตัวเป็นอินพุต
  เรียกฟังก์ชัน gcd() เพื่อหา gcd ของ n ตัวเลข
  เรียกฟังก์ชัน lcm() เพื่อหา lcm ของ n ตัวเลข
  
  gcd(number1, number2)
  ประกาศ r, a, b
  กำหนด r=0
  a = (number1 > number2) ? number1 : number2
  b = (number1 < number2) ? number1 : number2
  r = b
  While (a mod b != 0)
    r = a mod b
    a = b
    b = r
  Return r
  
  lcm(number1, number2)
  ประกาศ a
  a = (number1 > number2) ? number1 : number2
  While(true)
    If (a mod number1 == 0 and a mod number2 == 0)
      Return a
    Increment a
  Done
สิ้นสุด

โค้ดตัวอย่าง

#include <iostream>
using namespace std;

int gcd(int m, int n) {
    int r = 0, a, b;
    a = (m > n) ? m : n;
    b = (m < n) ? m : n;
    r = b;
    while (a % b != 0) {
        r = a % b;
        a = b;
        b = r;
    }
    return r;
}

int lcm(int m, int n) {
    int a;
    a = (m > n) ? m : n;
    while (true) {
        if (a % m == 0 && a % n == 0)
            return a;
        ++a;
    }
}

int main(int argc, char **argv) {
    cout << "Enter the two numbers: ";
    int m, n;
    cin >> m >> n;
    cout << "The GCD of two numbers is: " << gcd(m, n) << endl;
    cout << "The LCM of two numbers is: " << lcm(m, n) << endl;
    return 0;
}

ผลลัพธ์ตัวอย่าง

Enter the two numbers: 7 6
The GCD of two numbers is: 1
The LCM of two numbers is: 42