用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;
   }
   //现在n是奇数，所以如果我们将n加2，所有数字都将是奇数
   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