এখানে আমরা দেখব কীভাবে আমরা দুটি সংখ্যার কমন ডিভাইজরের সংখ্যা বের করতে পারি। আমরা সব কমন ডিভাইজর বের করব না, বরং আমরা গণনা করব কতগুলো কমন ডিভাইজর আছে। যদি দুটি সংখ্যা ১২ এবং ২৪ হয়, তবে কমন ডিভাইজরগুলো হলো 1, 2, 3, 4, 6, 12। তাই ৬টি কমন ডিভাইজর আছে, তাই উত্তর হবে ৬।
অ্যালগরিদম
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); // a এবং b-এর gcd বের করুন
int count = 0;
for (int i = 1; i <= sqrt(gcd_val); i++) {
if (gcd_val % i == 0) { // যখন 'i' n-এর ফ্যাক্টর
if (gcd_val / i == i) // যদি দুটি সংখ্যা একই হয়
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
