সমস্যা বিবৃতি
একটি পূর্ণসংখ্যা N দেওয়া হয়েছে। সর্বনিম্ন সংখ্যক বর্গ মুক্ত ভাজক খুঁজুন।
N-এর ফ্যাক্টরাইজেশনে শুধুমাত্র সেইসব ভাজক থাকা উচিত যেগুলো পূর্ণ বর্গ নয়
উদাহরণ
যদি N =24 হয় তাহলে নিম্নরূপ −
3টি বর্গ মুক্ত গুণনীয়ক রয়েছেগুণনীয়ক =2 * 6 * 2
অ্যালগরিদম
- N এর বর্গমূল পর্যন্ত সমস্ত মৌলিক গুণনীয়ক খুঁজুন
- এখন, N এর বর্গমূলের থেকে কম বা সমান সমস্ত মৌলিক গুণনীয়ক বিবেচনা করুন এবং প্রতিটি মৌলিক গুণনীয়কের জন্য N সংখ্যায় এর সর্বোচ্চ শক্তি খুঁজুন (যেমন 24-এর মধ্যে 2-এর সর্বোচ্চ শক্তি 3)
- এখন, আমরা জানি যে যদি একটি মৌলিক গুণনীয়কের শক্তি 1-এর বেশি হয়, তবে এটিকে নিজের সাথে গোষ্ঠীভুক্ত করা যায় না (উদাহরণস্বরূপ 2-এর 24-এর মধ্যে 3-এর শক্তি, তাই 2 x 2 =4 বা 2 x 2 x 2 =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
