程序使用C ++中的中学过程查找两个数字的GCD或HCF

在本教程中，我们将讨论使用中学程序查找两个数字的GCD或HCF的程序。

为此，我们将提供两个数字。我们的任务是找到给定值的GCD（最大公约数）或HCF（最高公因数）。

示例

#include <bits/stdc++.h>
#define MAXFACTORS 1024
using namespace std;
//存储因式分解的结构
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;
}
//打印因素
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-
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