समस्या कथन
एक पूर्णांक N दिया है। वर्ग मुक्त भाजक की न्यूनतम संख्या ज्ञात कीजिए।
N के गुणनखंड में केवल वे भाजक शामिल होने चाहिए जो पूर्ण वर्ग नहीं हैं
उदाहरण
यदि N =24 है तो 3 वर्ग मुक्त गुणनखंड इस प्रकार हैं -
गुणनखंड =2 * 6 * 2
एल्गोरिदम
- N के वर्गमूल तक सभी अभाज्य गुणनखंड ज्ञात करें
- अब, N के वर्गमूल से कम या उसके बराबर सभी अभाज्य गुणनखंडों पर विचार करें और प्रत्येक अभाज्य गुणनखंड के लिए संख्या N में इसकी अधिकतम घात ज्ञात करें (जैसे 24 में 2 की अधिकतम घात 3 है)
- अब, हम जानते हैं कि यदि किसी अभाज्य गुणनखंड की घात N में 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