न्यूनतम संख्या खोजें जिससे विभाजित करने पर संख्या पूर्ण वर्ग बन जाए C++ में

मान लीजिए हमारे पास एक संख्या N है। हमें वह न्यूनतम संख्या खोजनी है जो N को विभाजित करके इसे पूर्ण वर्ग बना दे। तो यदि N = 50, तो न्यूनतम संख्या 2 है, क्योंकि 50 / 2 = 25, और 25 एक पूर्ण वर्ग है।

एक संख्या पूर्ण वर्ग होती है यदि उसके अभाज्य गुणनखंडों की घात सम हो। तो हम N के अभाज्य गुणनखंड खोजने की कोशिश करेंगे, और प्रत्येक अभाज्य गुणनखंड की घात खोजेंगे। उन सभी अभाज्य गुणनखंडों को खोजें और गुणा करें जिनकी घात विषम है।

उदाहरण

#include <iostream>
#include <cmath>
using namespace std;

int findMinimumNumberToDivide(int n) {
    int prime_factor_count = 0, min_divisor = 1;
    while (n % 2 == 0) {
        prime_factor_count++;
        n /= 2;
    }
    if (prime_factor_count % 2)
        min_divisor *= 2;
    for (int i = 3; i <= sqrt(n); i += 2) {
        prime_factor_count = 0;
        while (n % i == 0) {
            prime_factor_count++;
            n /= i;
        }
        if (prime_factor_count % 2)
            min_divisor *= i;
    }
    if (n > 2)
        min_divisor *= n;
    return min_divisor;
}

int main() {
    int n = 108;
    cout << "Minimum number to divide is: " << findMinimumNumberToDivide(n) << endl;
}

आउटपुट

Minimum number to divide is: 3