C++ में मिडिल स्कूल प्रक्रिया का उपयोग करते हुए दो संख्याओं का 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