Ước chung của hai số là ước của cả hai số đó.
Ví dụ, các ước của 12 là 1, 2, 3, 4, 6, 12. Các ước của 18 là 1, 2, 3, 6, 9, 18. Như vậy, ước chung của 12 và 18 là 1, 2 , 3, 6. Số lớn nhất trong số này, có lẽ không có gì đáng ngạc nhiên, được gọi là của 12 và 18. Kí hiệu toán học thông thường cho ước chung lớn nhất của hai số nguyên a và b được ký hiệu là (a, b). Do đó, (12, 18) =6.
Ước số chung lớn nhất quan trọng vì nhiều lý do. Ví dụ, nó có thể được sử dụng để tính toán hai số, tức là, số nguyên dương nhỏ nhất là bội của những số này. Bội số chung nhỏ nhất của các số a và b có thể được tính là a * b * (a, b)
Ví dụ:bội số chung nhỏ nhất của 12 và 18 là12 * 18 * (12, 18) =12 * 18 * 6
Input: 4, 10, 16, 14 Output: 2
Giải thích
GCD của hai hoặc nhiều số nguyên là số nguyên lớn nhất có thể chia chính xác cả hai số (không có phần dư).
Ví dụ
#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;
} Đầu ra
4