โปรแกรม C สำหรับ Basic Euclidean Algorithm หา GCD

ที่นี่เราจะดู Euclidean Algorithm หา GCD (Greatest Common Divisor) ของสองจำนวน มี 2 แนวทาง: Iterative และ Recursive ที่นี่ใช้ Recursive

อัลกอริทึม

EuclideanAlgorithm(a, b)

begin
    if a is 0, then
        return b
    end if
    return gcd(b mod a, a)
end

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

#include <iostream>
using namespace std;

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

int main() {
    int a, b;
    cout << "Enter two numbers: ";
    cin >> a >> b;
    cout << "GCD " << euclideanAlgorithm(a, b);
}

ผลลัพธ์

Enter two numbers: 12 16
GCD 4