मान लीजिए हमारे पास एक संख्या 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