Computer >> 컴퓨터 >  >> 프로그램 작성 >> C++

두 숫자의 공약수를 위한 C++ 프로그램?

<시간/>

여기서는 두 수의 공약수를 구하는 방법을 알아보겠습니다. 모든 공약수를 찾지는 않겠지만 공약수가 몇 개인지 계산할 것입니다. 두 숫자가 12와 24와 같으면 공약수는 1, 2, 3, 4, 6, 12입니다. 따라서 공약수가 6개이므로 답은 6입니다.

알고리즘

countCommonDivisor(a, b)

begin
   count := 0
   gcd := gcd of a and b
   for i := 1 to square root of gcd, do
      if gcd is divisible by 0, then
         if gcd / i = i, then
            count := count + 1
         else
            count := count + 2
         enf if
      end if
   done
   return count
end

예시

#include<iostream>
#include<cmath>
using namespace std;
int gcd(int a, int b) {
   if (a == 0)
      return b;
   return gcd(b%a, a);
}
int countCommonDivisors(int a,int b) {
   int gcd_val = gcd(a, b); //get gcd of a and b
   int count = 0;
   for (int i=1; i<=sqrt(gcd_val); i++) {
      if (gcd_val%i==0) { // when'i' is factor of n
         if (gcd_val/i == i) //if two numbers are same
            count += 1;
         else
            count += 2;
      }
   }
   return count;
}
main() {
   int a = 12, b = 24;
   cout << "Total common divisors: " << countCommonDivisors(a, b);
}

출력

The differences array: 6 5 10 1