โปรแกรมหาตัวหารร่วมมาก (GCD/HCF) ของสองตัวเลขด้วยขั้นตอนวิธี Middle School ใน C++

ในบทช่วยสอนนี้ เราจะพูดถึงโปรแกรมหาตัวหารร่วมมาก (GCD) หรือ HCF ของสองตัวเลขด้วยขั้นตอนวิธี Middle School (การแยกตัวประกอบเฉพาะ)

เราจะได้รับสองตัวเลข งานคือหา GCD (ตัวหารร่วมมากที่สุด) หรือ HCF สำหรับค่าที่กำหนด

ตัวอย่างโค้ด

#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* factorization) {
    int i, j = 1, n = x, c = 0, 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) {
    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 min, i = 1, j = 1, x = 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 10 = 1*2*5 Prime factor of 15 = 1*3*5 5