ตัวหารร่วมของสองจำนวนคือจำนวนที่หารทั้งสองจำนวนลงตัว
ตัวอย่าง ตัวหารของ 12 คือ 1, 2, 3, 4, 6, 12 ตัวหารของ 18 คือ 1, 2, 3, 6, 9, 18 ดังนั้นตัวหารร่วมของ 12 และ 18 คือ 1, 2, 3, 6 ตัวที่มากที่สุดเรียกว่า GCD ของ 12 และ 18 สัญลักษณ์ทางคณิตศาสตร์คือ (a, b) ดังนั้น (12, 18) = 6
GCD สำคัญหลายเหตุผล เช่น คำนวณ LCM (ตัวคูณร่วมน้อย) ของสองจำนวน LCM ของ a และ b คำนวณได้จาก a*b/(a, b)
ตัวอย่าง LCM ของ 12 และ 18 คือ 12*18/6 = 36
Input: 4, 10, 16, 14 Output: 2
คำอธิบาย
GCD ของสองจำนวนเต็มขึ้นไป คือจำนวนเต็มที่ใหญ่ที่สุดที่หารทั้งสองจำนวนลงตัว (ไม่มีเศษ)
ตัวอย่างโค้ด
#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;
}
ผลลัพธ์
2
