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