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