C++에서 중학교 절차를 사용하여 두 숫자의 GCD 또는 HCF를 찾는 프로그램

이 튜토리얼에서는 중학교 절차를 사용하여 두 숫자의 GCD 또는 HCF를 찾는 프로그램에 대해 논의할 것입니다.

이를 위해 두 개의 숫자가 제공됩니다. 우리의 임무는 주어진 값에 대한 GCD(최대공약수) 또는 HCF(최고공약수)를 찾는 것입니다.

예시

#include <bits/stdc++.h>
#define MAXFACTORS 1024
using namespace std;
//structure to store factorization
typedef struct{
   int size;
   int factor[MAXFACTORS + 1];
   int exponent[MAXFACTORS + 1];
} FACTORIZATION;
void FindFactorization(int x, FACTORIZATION* factorization){
   int i, j = 1;
   int n = x, c = 0;
   int k = 1;
   factorization->factor[0] = 1;
   factorization->exponent[0] = 1;
   for (i = 2; i <= n; i++) {
      c = 0;
      while (n % i == 0) {
         c++;
         n = n / i;
      }
      if (c > 0) {
         factorization->exponent[k] = c;
         factorization->factor[k] = i;
         k++;
      }
   }
   factorization->size = k - 1;
}
//printing the factors
void DisplayFactorization(int x, FACTORIZATION factorization){
   int i;
   cout << "Prime factor of << x << = ";
   for (i = 0; i <= factorization.size; i++) {
      cout << factorization.factor[i];
      if (factorization.exponent[i] > 1)
         cout << "^" << factorization.exponent[i];
      if (i < factorization.size)
         cout << "*";
      else
         cout << "\n";
   }
}
//gcd using Middle School procedure
int gcdMiddleSchoolProcedure(int m, int n){
   FACTORIZATION mFactorization, nFactorization;
   int r, mi, ni, i, k, x = 1, j;
   FindFactorization(m, &mFactorization);
   DisplayFactorization(m, mFactorization);
   FindFactorization(n, &nFactorization);
   DisplayFactorization(n, nFactorization);
   int min;
   i = 1;
   j = 1;
   while (i <= mFactorization.size && j <= nFactorization.size) {
      if (mFactorization.factor[i] < nFactorization.factor[j])
         i++;
      else if (nFactorization.factor[j] < mFactorization.factor[i])
         j++;
      else{
         min = mFactorization.exponent[i] > nFactorization.exponent[j] ? nFactorization.exponent[j] : mFactorization.exponent[i];
         x = x * mFactorization.factor[i] * min;
         i++;
         j++;
      }
   }
   return x;
}
int main(){
   int m = 10, n = 15;
   cout << "GCD(" << m << ", " << n << ") = " << gcdMiddleSchoolProcedure(m, n);
   return (0);
}

출력

GCD(10, 15) = Prime factor of << x << = 1*2*5
Prime factor of << x << = 1*3*5
5