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