โปรแกรม C++ หาตัวหารร่วมมากที่สุด (GCD)

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

ตัวอย่าง: ตัวเลข 45 และ 27

45 = 5 × 3 × 3
27 = 3 × 3 × 3

ดังนั้น GCD ของ 45 และ 27 คือ 9

วิธีที่ 1: อัลกอริทึมยุคลิด (Euclidean Algorithm) แบบ Recursive

#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 = 105, b = 30;
    cout << "GCD of " << a << " and " << b << " is " << gcd(a, b);
    return 0;
}

ผลลัพธ์

GCD of 105 and 30 is 15

ฟังก์ชัน gcd() เป็นฟังก์ชันแบบเรียกซ้ำ (recursive) รับพารามิเตอร์ a และ b หาก b เท่ากับ 0 จะคืนค่า a มิฉะนั้นจะเรียกตัวเองใหม่ด้วยค่า b และ a % b

วิธีที่ 2: ใช้การลบซ้ำ (Subtraction Method)

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    if (a == 0 || b == 0)
        return 0;
    else if (a == b)
        return a;
    else if (a > b)
        return gcd(a - b, b);
    else
        return gcd(a, b - a);
}

int main() {
    int a = 105, b = 30;
    cout << "GCD of " << a << " and " << b << " is " << gcd(a, b);
    return 0;
}

ผลลัพธ์

GCD of 105 and 30 is 15

วิธีนี้ใช้หลักการลบค่าที่น้อยกว่าออกจากค่าที่มากกว่าซ้ำๆ จนกว่าทั้งสองจะเท่ากัน ซึ่งก็คือ GCD