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