C++ में मिडिल स्कूल प्रक्रिया द्वारा दो संख्याओं का GCD/HCF

मिडिल स्कूल प्रक्रिया (अभाज्य गुणनखंड) द्वारा GCD खोजें: दोनों संख्याओं का अभाज्य गुणनखंड करें, सामान्य गुणनखंडों को उनके न्यूनतम घात के साथ गुणा करें।

उदाहरण: 10 और 15 → अभाज्य गुणनखंड: 10=2×5, 15=3×5 → GCD = 5।

C++ कार्यान्वयन

#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, k = 1;
    int n = x, c = 0;
    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) {
    cout << "Prime factor of " << x << " = ";
    for (int 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";
    }
}

int gcdMiddleSchoolProcedure(int m, int n) {
    FACTORIZATION mFactorization, nFactorization;
    FindFactorization(m, &mFactorization);
    DisplayFactorization(m, mFactorization);
    FindFactorization(n, &nFactorization);
    DisplayFactorization(n, nFactorization);
    int x = 1;
    int 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 {
            int min = (mFactorization.exponent[i] > nFactorization.exponent[j]) ? 
                      nFactorization.exponent[j] : mFactorization.exponent[i];
            for (int k = 0; k < min; k++) x *= mFactorization.factor[i];
            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 10 = 1*2*5 Prime factor of 15 = 1*3*5 5