C++에서 최소 제곱 자유 제수 수

문제 설명

주어진 정수 N. 제곱 자유 제수의 최소 수를 찾으십시오.

N의 인수분해는 완전제곱수가 아닌 제수로만 구성되어야 합니다.

예

N =24이면 다음과 같이 3개의 제곱 자유 인수가 있습니다. -

요인 =2 * 6 * 2

알고리즘

• N의 제곱근까지 모든 소인수 찾기
• 이제 N의 제곱근보다 작거나 같은 모든 소인수를 고려하고 각 소인수에 대해 N 수에서 최대 거듭제곱을 찾습니다(예:24에서 2의 최대 거듭제곱은 3임).
• 이제 우리는 소인수의 거듭제곱이 N에서 1보다 크면 그 자체로 그룹화할 수 없다는 것을 압니다(예:2는 24에서 3의 거듭제곱을 가지므로 2 x 2 =4 또는 2 x 2 x 2 =8은 24의 인수분해에서 발생할 수 없습니다. 둘 다 제곱이 아니므로 완전제곱수로 나눌 수 있기 때문입니다.
• 그러나 다른 소인수와 함께 그룹화된 소인수(단 한 번만)는 절대 완전제곱수로 나눌 수 없습니다.
• 이것은 답이 숫자 N에 있는 모든 소인수의 최대 거듭제곱이 될 것이라는 직관을 제공합니다.

예

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
#define MAX 1005
void getPrimes(vector<int>& primes) {
   bool prime[MAX];
   memset(prime, true, sizeof(prime));
   for (int p = 2; p * p < MAX; p++) {
      if (prime[p] == true) {
         for (int i = p * 2; i < MAX; i += p)
            prime[i] = false;
      }
   }
   for (int p = 2; p < MAX; p++)
   if (prime[p])
   primes.push_back(p);
}
int getMinimumSquareFreeDivisors(int n) {
   vector<int> primes;
   getPrimes(primes);
   int maxCnt = 0;
   for (int i = 0; i < primes.size() && primes[i] * primes[i] <= n; i++) {
      if (n % primes[i] == 0) {
         int tmp = 0;
         while (n % primes[i] == 0) {
            tmp++;
            n /= primes[i];
         }
         maxCnt = max(maxCnt, tmp);
      }
   }
   if (maxCnt == 0)
   maxCnt = 1;
   return maxCnt;
}
int main() {
   int n = 24;
   cout << "Minimum number of square free divisors = " << getMinimumSquareFreeDivisors(n) << endl;
   return 0;
}

출력

위의 프로그램을 컴파일하고 실행할 때. 다음 출력을 생성합니다 -

Minimum number of square free divisors = 3