ดังที่เราทราบ HCF หรือ GCD สามารถคำนวณได้อย่างง่ายดายโดยใช้อัลกอริทึมแบบยุคลิด แต่ที่นี่เราจะมาดูวิธีการสร้าง GCD หรือ HCF โดยไม่ต้องใช้อัลกอริทึมแบบยุคลิดหรืออัลกอริธึมแบบเรียกซ้ำใดๆ สมมติว่ามีตัวเลขสองตัวเป็น 16 และ 24 GCD ของสองตัวนี้คือ 8
วิธีการนี้ง่าย หากจำนวนที่มากกว่าของสองตัวนี้หารด้วยจำนวนที่น้อยกว่า นั่นคือ HCF มิฉะนั้นจะเริ่มต้นจาก (เล็กกว่า / 2) ถึง 1 หากองค์ประกอบปัจจุบันหารจำนวนทั้งสอง นั่นคือ HCF
ตัวอย่าง
#include <iostream>
using namespace std;
int gcd(int a, int b) {
int min_num = min(a, b);
if (a % min_num == 0 && b % min_num == 0)
return min_num;
for (int i = min_num / 2; i >= 2; i--) {
if (a % i == 0 && b % i == 0)
return i;
}
return 1;
}
int main() {
int a = 16, b = 24;
cout << "HCF: "<< gcd(a, b);
} ผลลัพธ์
HCF: 8
