Tìm BCNN của nhiều số (mảng) không dùng UCLN trong C++

Tìm BCNN (Least Common Multiple) của tất cả phần tử trong mảng mà không dùng phép UCLN (GCD). Ví dụ mảng {4, 6, 12, 24, 30} → BCNN = 120.

BCNN của hai số a, b: bắt đầu từ max(a,b), tăng dần cho đến khi chia hết cho cả a và b. Áp dụng lặp: BCNN của mảng = BCNN(BCNN(arr[0], arr[1]), arr[2])...

Ví dụ

#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);
}

Kết quả

LCM of array elements: 120