C++で平方フリー約数の最小個数を求める方法

問題文

整数 N が与えられます。「平方フリー約数(完全平方数ではない約数)」のみを使って N を因数分解するとき、必要となる約数の最小個数を求めてください。

つまり、N の因数分解には、完全平方数とならない約数だけを使用する必要があります。

例

N = 24 の場合、平方フリーな因子は以下のように 3 つになります。

因数 = 2 × 6 × 2

アルゴリズム

• まず、N の平方根までのすべての素因数を求めます。
• 次に、N の平方根以下のすべての素因数について、それぞれ N における最大の冪指数を調べます(例：24 における 2 の最大冪指数は 3)。
• ある素因数が N の中で 1 より大きい冪を持つ場合、その素因数同士を掛け合わせることはできません(例：24 における 2 の冪指数は 3 ですが、2 × 2 = 4 や 2 × 2 × 2 = 8 はどちらも平方フリーではないため、24 の因数分解には使えません)。これらは必ず何らかの完全平方数で割り切れてしまうからです。
• 一方、異なる素因数どうしを(1 回だけ)掛け合わせた積は、いかなる完全平方数でも割り切れません。
• この性質から、「答えは N を構成するすべての素因数の最大冪指数の中で最も大きい値になる」と推察できます。

実装例(C++)

#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