หา LCM ของ Array Numbers โดยไม่ใช้ GCD ใน C++

เรามี Array A ต้องการหา LCM ของทุก Elements โดยไม่ใช้ GCD Operation ถ้า Array คือ {4, 6, 12, 24, 30} LCM จะเป็น 120

LCM ของ 2 จำนวนคำนวณง่าย อัลกอริทึม:

getLCM(a, b)

begin
    if a > b, then m := a, otherwise m := b
    while true do
        if m divisible by both a and b, then return m
        m := m + 1
    done
end

ใช้ Function นี้หา LCM ของ 2 ตัวแรก แล้วนำผลลัพธ์ไปหา LCM กับตัวถัดไป จนครบ Array

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

#include <iostream>
using namespace std;

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

int getLCMArray(int arr[], int n) {
    int lcm = getLCM(arr[0], arr[1]);
    for(int i = 2; i < n; i++) {
        lcm = getLCM(lcm, arr[i]);
    }
    return lcm;
}

int main() {
    int arr[] = {4, 6, 12, 24, 30};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "LCM of array elements: " << getLCMArray(arr, n);
}

ผลลัพธ์

LCM of array elements: 120