সংখ্যাকে সম্পূর্ণ বর্গ করতে ন্যূনতম কত দিয়ে ভাগ করতে হবে তা বের করা 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