หาตัวหารร่วมมาก (GCD) ของสองจำนวน

บทนำ

ในคณิตศาสตร์ ตัวหารร่วมมาก (Greatest Common Divisor - GCD) คือจำนวนเต็มที่มากที่สุดที่หารทั้งสองจำนวนลงตัว เงื่อนไขคือทั้งสองจำนวนต้องไม่เป็นศูนย์

เราจะใช้ยุคลิดอัลกอริทึม (Euclidean Algorithm) ในการหา GCD

อินพุตและเอาต์พุต

Input: สองจำนวน 51 และ 34
Output: GCD คือ: 17

อัลกอริทึม

findGCD(a, b)
Input: สองจำนวน a และ b
Output: GCD ของ a และ b

Begin
    if a = 0 หรือ b = 0, then
        return 0
    if a = b, then
        return b
    if a > b, then
        return findGCD(a-b, b)
    else
        return findGCD(a, b-a)
End

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

#include <iostream>
using namespace std;

int findGCD(int a, int b) {
    // สมมติ a มากกว่า b
    if (a == 0 || b == 0)
        return 0;  // เนื่องจาก a และ b เป็น 0 ตัวหารมากที่สุดก็คือ 0
    if (a == b)
        return b;  // เมื่อทั้งสองจำนวนเท่ากัน
    if (a > b)
        return findGCD(a-b, b);
    else
        return findGCD(a, b-a);
}

int main() {
    int a, b;
    cout << "Enter Two numbers to find GCD: ";
    cin >> a >> b;
    cout << "The GCD is: " << findGCD(a,b);
}

ผลลัพธ์

Enter Two numbers to find GCD: 51 34
The GCD is: 17