โปรแกรม C++ หาตัวหารร่วมของสองจำนวน

ที่นี่เราจะดูวิธีหาจำนวนตัวหารร่วมของสองจำนวน เราจะไม่หาตัวหารร่วมทั้งหมด แต่จะนับว่ามีตัวหารร่วมกี่ตัว ถ้าสองจำนวนคือ 12 และ 24 ตัวหารร่วมคือ 1, 2, 3, 4, 6, 12 ดังนั้นมี 6 ตัวหารร่วม คำตอบคือ 6

อัลกอริทึม

countCommonDivisor(a, b)

begin
    count := 0
    gcd := gcd of a and b
    for i := 1 to square root of gcd, do
        if gcd is divisible by i, then
            if gcd / i = i, then
                count := count + 1
            else
                count := count + 2
            end if
        end if
    done
    return count
end

ตัวอย่าง

#include<iostream>
#include<cmath>
using namespace std;

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

int countCommonDivisors(int a, int b) {
    int gcd_val = gcd(a, b); // get gcd of a and b
    int count = 0;
    for (int i = 1; i <= sqrt(gcd_val); i++) {
        if (gcd_val % i == 0) { // when 'i' is factor of n
            if (gcd_val / i == i) // if two numbers are same
                count += 1;
            else
                count += 2;
        }
    }
    return count;
}

int main() {
    int a = 12, b = 24;
    cout << "Total common divisors: " << countCommonDivisors(a, b);
}

ผลลัพธ์

Total common divisors: 6