এই টিউটোরিয়ালে, আমরা মধ্য বিদ্যালয় পদ্ধতি ব্যবহার করে দুটি সংখ্যার 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
