ตัวหารร่วมมาก (HCF / GCD)
ตัวหารร่วมมากคือจำนวนเต็มบวกที่มากที่สุดที่หารตัวเลขทั้งสองลงตัว เรียกอีกอย่างว่า Greatest Common Divisor (GCD) หรือ Greatest Common Measure (GCM)
ตัวอย่าง: HCF ของ 12 และ 16
ตัวหารของ 12: 1, 2, 3, 4, 6, 12 ตัวหารของ 16: 1, 2, 4, 8, 16 HCF = 4
ตัวคูณร่วมน้อย (LCM)
ตัวคูณร่วมน้อยคือจำนวนเต็มบวกที่น้อยที่สุดที่หารด้วยตัวเลขทั้งสองลงตัว
ตัวอย่าง: LCM(2,3) = 6, LCM(6,10) = 30
ความสัมพันธ์ระหว่าง HCF และ LCM
สำหรับจำนวนเต็มบวก a, b:
a * b = HCF(a,b) * LCM(a,b)
ดังนั้น LCM = (a * b) / HCF
อัลกอริทึม Euclidean Algorithm (หา HCF)
วิธีที่มีประสิทธิภาพที่สุด:
while (b != 0) {
temp = b;
b = a % b;
a = temp;
}
// HCF = aตัวอย่างโปรแกรม: หา HCF และ LCM
#include <stdio.h>
int main() {
int num1, num2, x, y, temp, gcd, lcm;
printf("ป้อนจำนวนเต็ม 2 ตัว: ");
scanf("%d%d", &x, &y);
num1 = x;
num2 = y;
// Euclidean algorithm
while (num2 != 0) {
temp = num2;
num2 = num1 % num2;
num1 = temp;
}
gcd = num1;
lcm = (x * y) / gcd;
printf("GCD ของ %d และ %d = %d\\n", x, y, gcd);
printf("LCM ของ %d และ %d = %d\\n", x, y, lcm);
return 0;
}ผลลัพธ์ตัวอย่าง
Run 1: ป้อนจำนวนเต็ม 2 ตัว: 6 12 GCD ของ 6 และ 12 = 6 LCM ของ 6 และ 12 = 12 Run 2: ป้อนจำนวนเต็ม 2 ตัว: 24 36 GCD ของ 24 และ 36 = 12 LCM ของ 24 และ 36 = 72
การปรับปรุงโค้ด (Best Practices)
-
-
-
-
