C++에서 완전제곱수를 만들기 위해 나눌 최소수 찾기

숫자 N이 있다고 가정합니다. N을 완전제곱수로 나누는 최소 숫자를 찾아야 합니다. 따라서 N =50이면 50 / 2 =25이므로 최소 수는 2이고 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