หา HCF (GCD) ของสองจำนวนโดยไม่ใช้การเรียกซ้ำหรืออัลกอริทึมยุคลิด ใน C++

บทนำ

ปกติ HCF หรือ GCD คำนวณได้ง่ายด้วยอัลกอริทึมยุคลิด แต่ที่นี่จะแสดงวิธีหา GCD โดยไม่ใช้การเรียกซ้ำ (recursion) และไม่ใช่อัลกอริทึมยุคลิด

ตัวอย่าง: จำนวน 16 และ 24 → GCD = 8

แนวคิด

1. หาจำนวนที่น้อยกว่าระหว่างสองจำนวน
2. ถ้าจำนวนมากกว่าหารด้วยจำนวนน้อยลงตัว → จำนวนน้อยคือ HCF
3. มิฉะนั้น วนลูปจาก (จำนวนน้อย / 2) ลงมาที่ 1 ถ้าตัวเลขไหนหารทั้งสองจำนวนลงตัว → นั้นคือ HCF

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

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    int min_num = min(a, b);
    if (a % min_num == 0 && b % min_num == 0)
        return min_num;
    for (int i = min_num / 2; i >= 2; i--) {
        if (a % i == 0 && b % i == 0)
            return i;
    }
    return 1;
}

int main() {
    int a = 16, b = 24;
    cout << "HCF: " << gcd(a, b);
    return 0;
}

ผลลัพธ์

HCF: 8