C++での平方フリー除数の最小数

問題の説明

整数Nが与えられます。平方自由除数の最小数を見つけます。

Nの因数分解は、完全な二乗ではない約数のみで構成する必要があります

例

N =24の場合、次の3つの正方形の自由係数があります-

因数=2* 6 * 2

アルゴリズム

• Nの平方根までのすべての素因数を見つける
• ここで、Nの平方根以下のすべての素因数を検討し、各素因数について、その最大累乗を数Nで見つけます（24の2の最大累乗は3です）
• これで、素因数の累乗がNで1より大きい場合、それ自体とグループ化できないことがわかりました（たとえば、2の累乗は24で3であるため、2 x 2=4または2x2 x 2 =8は、24の因数分解では発生しません。これは、両方とも平方フリーではないためです）。これは、完全な平方で割り切れるからです。
• ただし、別の素因数とグループ化された素因数（1回のみ）は、完全な正方形で割り切れることはありません。
• これにより、答えは数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