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