সমস্যা বিবরণ
একটি ইন্টিজার N দেওয়া আছে। মিনিমাম নাম্বার অফ স্কয়ার-ফ্রি ডিভাইজর বের করুন।
N-এর ফ্যাক্টরাইজেশন শুধু সেই ডিভাইজরগুলো দিয়ে গঠিত হতে হবে যা ফুল স্কয়ার নয়।
উদাহরণ
যদি N = 24 হয়, তবে ৩টি স্কয়ার-ফ্রি ফ্যাক্টর থাকবে:
ফ্যাক্টরস = 2 * 6 * 2
অ্যালগরিদম
- N-এর বর্গমূল পর্যন্ত সব প্রাইম ফ্যাক্টর বের করুন
- এখন, N-এর বর্গমূল থেকে কম বা সমান সব প্রাইম ফ্যাক্টর কনসিডার করুন এবং প্রতিটি প্রাইম ফ্যাক্টরের জন্য N-এ এর ম্যাক্সিমাম পাওয়ার বের করুন (যেমন 24-এ ২-এর ম্যাক্স পাওয়ার ৩)
- আমরা জানি, যদি একটি প্রাইম ফ্যাক্টরের পাওয়ার N-এ ১-এর চেয়ে বড় হয়, তবে সেটি নিজের সাথে গ্রুপ করা যাবে না (যেমন 24-এ ২-এর পাওয়ার ৩, তাই 2x2=4 বা 2x2x2=8, 24-এর ফ্যাক্টরাইজেশনে থাকতে পারবে না কারণ সেগুলো স্কয়ার-ফ্রি নয়) যেহেতু সেগুলো কোনো পারফেক্ট স্কয়ার দিয়ে ডিভাইডেবল হবে
- কিন্তু একটি প্রাইম ফ্যাক্টর অন্য প্রাইম ফ্যাক্টরের সাথে (শুধু একবার) গ্রুপ করা হলে সেটি কোনো পারফেক্ট স্কয়ার দিয়ে ডিভাইডেবল হবে না
- এটি আমাদের ইন্টুইশন দেয় যে আন্সার হবে N-এ সব প্রাইম ফ্যাক্টরের ম্যাক্সিমাম পাওয়ারগুলোর ম্যাক্সিমাম
উদাহরণ
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
#define MAX 1005
void getPrimes(vector<int>& primes) {
bool prime[MAX];
memset(prime, true, sizeof(prime));
for (int p = 2; p * p < MAX; p++) {
if (prime[p] == true) {
for (int i = p * 2; i < MAX; i += p)
prime[i] = false;
}
}
for (int p = 2; p < MAX; p++)
if (prime[p])
primes.push_back(p);
}
int getMinimumSquareFreeDivisors(int n) {
vector<int> primes;
getPrimes(primes);
int maxCnt = 0;
for (int i = 0; i < primes.size() && primes[i] * primes[i] <= n; i++) {
if (n % primes[i] == 0) {
int tmp = 0;
while (n % primes[i] == 0) {
tmp++;
n /= primes[i];
}
maxCnt = max(maxCnt, tmp);
}
}
if (maxCnt == 0)
maxCnt = 1;
return maxCnt;
}
int main() {
int n = 24;
cout << "Minimum number of square free divisors = " << getMinimumSquareFreeDivisors(n) << endl;
return 0;
}
আউটপুট
যখন আপনি উপরের প্রোগ্রাম কম্পাইল ও এক্সিকিউট করবেন। এটি নিচের আউটপুট জেনারেট করবে:
Minimum number of square free divisors = 3
