หาตัวหารร่วมมาก (HCF/GCD) แบบวนซ้ำใน C++

หาตัวหารร่วมมาก (HCF/GCD) ของสองจำนวนด้วยวิธีการลบซ้ำ (Euclidean algorithm แบบ subtraction)

ตัวอย่าง: 60 และ 96 → 12

วิธีแก้ปัญหา (Subtraction-based Euclidean Algorithm)

1. while a ≠ b:
   • ถ้า a > b → a = a - b
   • มิฉะนั้น → b = b - a
2. คืนค่า a (หรือ b)

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

int get_HCF(int a, int b) {
    while (a != b) {
        if (a > b) a = a - b;
        else b = b - a;
    }
    return a;
}

int main() {
    int a = 60, b = 96;
    cout << get_HCF(a, b) << endl;
    return 0;
}

Output

12