ধরুন আমাদের একটি সংখ্যা 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
