C++ এ প্রদত্ত GCD এবং LCM সহ যেকোনো জোড়া খুঁজুন

এই বিভাগে আমরা দেখব কিভাবে প্রদত্ত GCD এবং LCM মান ব্যবহার করে জোড়ার সংখ্যা পাওয়া যায়। ধরুন GCD এবং LCM মান হল 2 এবং 12। এখন সংখ্যার সম্ভাব্য জোড়া হল (2, 12), (4, 6), (6, 4) এবং (12, 2)। তাই আমাদের প্রোগ্রাম জোড়ার গণনা খুঁজে পাবে। সেটা হল 4.

এই সমস্যা সমাধানের কৌশল কী হবে তা বোঝার জন্য আসুন অ্যালগরিদম দেখি।

অ্যালগরিদম

countPairs(gcd, lcm):
Begin
   if lcm is nit divisible by gcd, then
      return 0
   temp := lcm/gcd
   c := primeFactorCount(temp)
   res := shift 1 to the left c number of times
   return res
End
primeFactorCount(n):
Begin
   count := 0
   until n is not odd, increase count and divide n by 2
   for i := 3, when i2 < n, increase i by 2, do
      if n is divisible by i, then
         increase count
         while n is divisible by i, do
            n := n / i
         done
      end if
   done
   if n > 2, then
      increase count by 1
   return count
End

উদাহরণ

#include<iostream>
#include<cmath>
using namespace std;
int primeFactorCount(int);
int countPairs(int gcd, int lcm) {
   if(lcm % gcd != 0)
      return 0;
   int temp = lcm/gcd;
   return (1 << primeFactorCount(temp));
}
int primeFactorCount(int n){
   int count = 0;
   if(n%2 == 0){ //if n is divisible by 0, enter into the next part
      count++;
      while(n%2 == 0)
      n = n/2;
   }
   //now n is odd, so if we increase n by 2, all numbers will be odd
   for(int i = 3; i*i <= n; i = i + 2){
      if(n%i == 0){ //if n is divisible by 0, enter into the next part
         count++;
         while(n%i == 0)
         n = n/i;
      }
   }
   if(n > 2)
   count++;
   return count;
}
int main() {
   cout << "Possible pairs of GCD = 2, and LCM = 12 is " <<countPairs(2, 12);
}

আউটপুট

Possible pairs of GCD = 2, and LCM = 12 is 4