เราจะมาดูกันว่าเราจะหาจำนวนตัวหารร่วมของตัวเลขสองตัวได้อย่างไร เราจะไม่พบตัวหารร่วมทั้งหมด แต่เราจะนับว่ามีตัวหารร่วมทั้งหมดกี่ตัว หากตัวเลขสองตัวเช่น 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 0, then if gcd / i = i, then count := count + 1 else count := count + 2 enf 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;
}
main() {
int a = 12, b = 24;
cout << "Total common divisors: " << countCommonDivisors(a, b);
} ผลลัพธ์
The differences array: 6 5 10 1
