Chương trình C++ tìm UCLN của nhiều số (hoặc mảng)

Ước chung của hai số là các số chia hết cho cả hai.

Ví dụ: ước của 12: 1,2,3,4,6,12. Ước của 18: 1,2,3,6,9,18. Ước chung: 1,2,3,6. Lớn nhất là UCLN(12,18)=6. Ký hiệu (a,b).

UCLN quan trọng để tính BCNN: a*b/(a,b). Ví dụ BCNN(12,18)=12*18/6=36.

Ví dụ

Input: 4, 10, 16, 14 
Output: 2

Giải thích

UCLN của hai hoặc nhiều số nguyên là số nguyên lớn nhất chia hết cho tất cả các số (không dư).

Ví dụ mã C++

#include <iostream> 
using namespace std; 

int gcd(int a, int b) { 
    int temp; 
    while (b > 0) { 
        temp = b; 
        b = a % b; 
        a = temp; 
    } 
    return a; 
} 

int main() { 
    int a[] = {4, 10, 16, 14}; 
    int n = 4; 
    int r = a[0]; 
    for (int i = 1; i < n; i++) 
        r = gcd(r, a[i]); 
    cout << r << endl; 
    return 0; 
}

Kết quả

2