Tìm số nhỏ nhất bị chia để một số trở thành hình vuông hoàn hảo trong C ++

Giả sử chúng ta có một số N. Chúng ta phải tìm số nhỏ nhất chia N để nó là một hình vuông hoàn hảo. Vì vậy, nếu N =50, thì số tối thiểu là 2, vì 50/2 =25 và 25 là một hình vuông hoàn hảo.

Một số là hình vuông hoàn hảo nếu nó có các thừa số chẵn. Vì vậy, chúng tôi sẽ cố gắng tìm các thừa số nguyên tố của N, và tìm lũy thừa của mỗi hệ số nguyên tố. Tìm và nhân tất cả các thừa số nguyên tố có lũy thừa là số lẻ.

Ví dụ

#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;
}

Đầu ra

Minimum number to divide is: 3