C++ में न्यूनतम स्क्वायर-फ्री डिवाइजर्स की संख्या

समस्या विवरण

एक इंटीजर N दिया गया है। न्यूनतम स्क्वायर-फ्री डिवाइजर्स की संख्या ढूंढें।

N का फैक्टराइज़ेशन केवल उन डिवाइजर्स से बना होना चाहिए जो पूर्ण वर्ग नहीं हैं।

उदाहरण

यदि N = 24 तो 3 स्क्वायर-फ्री फैक्टर हैं:

फैक्टर = 2 * 6 * 2

एल्गोरिदम

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