โปรแกรม C++ หาค่าตัวหารร่วมมาก (GCD) ด้วย Euclid Algorithm แบบ Recursive

GCD (Greatest Common Divisor) หรือ ตัวหารร่วมมาก คือ จำนวนเต็มบวกที่มากที่สุดที่หารทั้งสองจำนวนลงตัว

ตัวอย่าง

63 = 7 × 3 × 3
21 = 7 × 3
GCD(63, 21) = 21

หลักการ Euclidean Algorithm แบบ Recursive

หลักการคือ: GCD(a, b) = GCD(b, a % b) ทำซ้ำจน b = 0 แล้วคำตอบคือ a

โค้ดโปรแกรม

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

int main() {
    int a, b;
    cout << "Enter the values of a and b: ";
    cin >> a >> b;
    cout << "GCD of " << a << " and " << b << " is " << gcd(a, b);
    return 0;
}

ผลลัพธ์ตัวอย่าง

Enter the values of a and b: 105 30
GCD of 105 and 30 is 15

การทำงานทีละขั้นตอน (Trace)

gcd(105, 30)
→ gcd(30, 105%30=15)
→ gcd(15, 30%15=0)
→ return 15

ข้อดีของวิธี Recursive

• โค้ดสั้น กระชับ อ่านง่าย
• Time Complexity: O(log min(a,b)) - เร็วมาก
• ใช้ stack space เล็กน้อย (log n ระดับ)

เวอร์ชัน Iterative (ไม่ใช้ Recursion)

int gcd_iterative(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

ทั้งสองวิธีให้ผลลัพธ์เท่ากัน เลือกใช้ตามความชอบ