সমস্যা বিবরণ
দুটি সংখ্যার প্রাইম ফ্যাক্টরাইজেশন করে তাদের GCD বের করা (মিডল স্কুল পদ্ধতি)।
সমাধানের পদ্ধতি
- প্রতিটি সংখ্যার প্রাইম ফ্যাক্টরাইজেশন করুন।
- কমন প্রাইম ফ্যাক্টরগুলোর মিনিমাম এক্সপোনেন্ট নিয়ে গুণ করুন।
- ফলাফলটি GCD।
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, 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;
}
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";
}
}
int gcdMiddleSchoolProcedure(int m, int n) {
FACTORIZATION mFactorization, nFactorization;
FindFactorization(m, &mFactorization);
DisplayFactorization(m, mFactorization);
FindFactorization(n, &nFactorization);
DisplayFactorization(n, nFactorization);
int 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 {
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) = 5
ব্যাখ্যা
10 = 2 × 5
15 = 3 × 5
কমন: 5^1 = 5
জটিলতা
- সময়: O(√n) ফ্যাক্টরাইজেশনের জন্য
- স্থান: O(log n)
