C++で数Nを完全平方数にするための最小の除数を求める方法

ある数 N が与えられたとき、N を割り算することで完全平方数（平方数）にできる最小の数を求める問題を考えてみましょう。たとえば N = 50 の場合、答えは 2 です。50 ÷ 2 = 25 となり、25 は 5 × 5 で表される完全平方数だからです。

考え方

完全平方数とは、素因数分解したときにすべての素因数の指数が偶数になる数のことです。この性質を利用すると、次の手順で問題を解くことができます。

1. N を素因数分解し、それぞれの素因数の指数（べき乗）を調べる。
2. 指数が奇数になっている素因数をすべて見つけ、それらを掛け合わせる。

こうして得られた積こそが、N を完全平方数にするための最小の除数です。指数が奇数の素因数を一度だけ掛けてやれば、その指数が偶数に変わり、結果として数全体が完全平方数になるためです。

具体例：N = 108 の場合

• 108 = 2² × 3³ と素因数分解できる
• 2 の指数は 2（偶数）、3 の指数は 3（奇数）
• よって、掛けるべき最小の数は 3
• 実際に 108 ÷ 3 = 36 = 6² となり、完全平方数になります。

C++での実装例

#include<iostream>
#include<cmath>
using namespace std;

int findMinimumNumberToDivide(int n) {
    int prime_factor_count = 0, min_divisor = 1;

    // まず素因数 2 を処理
    while (n % 2 == 0) {
        prime_factor_count++;
        n /= 2;
    }
    // 2 の指数が奇数なら min_divisor に 2 を掛ける
    if (prime_factor_count % 2)
        min_divisor *= 2;

    // 3 以降の奇数の候補で素因数を探す
    for (int i = 3; i <= sqrt(n); i += 2) {
        prime_factor_count = 0;
        while (n % i == 0) {
            prime_factor_count++;
            n /= i;
        }
        // 指数が奇数なら min_divisor に i を掛ける
        if (prime_factor_count % 2)
            min_divisor *= i;
    }

    // ループ後に残った値は指数 1 の素因数なので処理する
    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

アルゴリズムのポイント

• 素因数分解：まず 2 で割り切れるだけ割り、その後は 3, 5, 7 と奇数を順に試します。
• 指数の判定：各素因数について割り切れた回数（指数）をカウントし、奇数かどうかを判定します。
• 残りの処理：ループ終了後に n > 2 が成り立つ場合は、n 自体が指数 1 の素因数として残っているため、min_divisor に掛けます。

この手法を使えば、O(√n) の計算量で効率よく答えを求めることができ、大きな数に対しても実用的な速度で動作します。