Chương trình tìm GCD/HCF bằng phương pháp nhân tử hóa (Middle School) trong C++

Tìm GCD bằng cách phân tích thừa số nguyên tố (phương pháp Middle School).

Thuật toán

• Phân tích 2 số thành thừa số nguyên tố với số mũ.
• GCD = tích các thừa số chung với số mũ nhỏ nhất.

Ví dụ triển khai (C++)

#include <bits/stdc++.h>
#define MAXFACTORS 1024
using namespace std;

struct FACTORIZATION {
    int size;
    int factor[MAXFACTORS + 1];
    int exponent[MAXFACTORS + 1];
};

void FindFactorization(int x, FACTORIZATION* f) {
    int n = x, k = 1;
    f->factor[0] = 1; f->exponent[0] = 1;
    for (int i = 2; i <= n; i++) {
        int c = 0;
        while (n % i == 0) { c++; n /= i; }
        if (c > 0) { f->exponent[k] = c; f->factor[k] = i; k++; }
    }
    f->size = k - 1;
}

void DisplayFactorization(int x, FACTORIZATION f) {
    cout << "Prime factor of " << x << " = ";
    for (int i = 0; i <= f.size; i++) {
        cout << f.factor[i];
        if (f.exponent[i] > 1) cout << "^" << f.exponent[i];
        if (i < f.size) cout << "*"; else cout << "\n";
    }
}

int gcdMiddleSchoolProcedure(int m, int n) {
    FACTORIZATION mF, nF;
    FindFactorization(m, &mF); DisplayFactorization(m, mF);
    FindFactorization(n, &nF); DisplayFactorization(n, nF);
    int x = 1, i = 1, j = 1;
    while (i <= mF.size && j <= nF.size) {
        if (mF.factor[i] < nF.factor[j]) i++;
        else if (nF.factor[j] < mF.factor[i]) j++;
        else {
            int mn = min(mF.exponent[i], nF.exponent[j]);
            x *= pow(mF.factor[i], mn);
            i++; j++;
        }
    }
    return x;
}

int main() {
    int m = 10, n = 15;
    cout << "GCD(" << m << ", " << n << ") = " << gcdMiddleSchoolProcedure(m, n);
    return 0;
}

Đầu ra

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