C++で数値がa^b（累乗）の形で表現できるかどうかを判定する方法

本記事では、与えられた数値が a^b のような累乗の形式で表現できるかどうかを判定する方法を解説します。例えば、125 は 5³ と表現できます。一方、91 はいかなる整数の累乗としても表現できません。

アルゴリズム

基本的な考え方は次の通りです。数値が 1 であれば常に真を返し、それ以外の場合は底となる候補 i を 2 から順に試していきます。対数の性質を利用して「i を何乗すると num になるか」を計算し、その結果がほぼ整数であれば、num は i の累乗として表現できると判断できます。

isRepresentPower(num):
Begin
    if num = 1, then return true
    for i := 2, i*i <= num, increase i by 1, do
        val := log(num) / log(i)
        if val - int(val) < 0.0000000001, then return true
    done
    return false
End

仕組みのポイント

log(num) / log(i) を計算すると、i を何乗すれば num に一致するかが求まります。この値の小数部分が十分に 0 に近い場合（ここでは誤差 0.00000001 未満）、num は整数 i の累乗であるとみなせます。また、ループ条件を i * i <= num としているのは、num が a^b（b ≥ 2）の形で表せるなら、その底 a は必ず √num 以下になるためです。これにより探索範囲を効率的に絞り込めます。

C++での実装例

#include<iostream>
#include<cmath>
using namespace std;
bool isRepresentPower(int num) {
    if (num == 1)
        return true;
    for (int i = 2; i * i <= num; i++) {
        double val = log(num) / log(i);
        if ((val - (int)val) < 0.00000001)
            return true;
    }
    return false;
}
int main() {
    int n = 125;
    cout << (isRepresentPower(n) ? "Can be represented" : "Cannot be represented");
}

実行結果

Can be represented

このプログラムでは n = 125 を渡しています。125 は 5³ に等しいため、「Can be represented（表現可能）」と出力されます。浮動小数点演算には微小な誤差が伴うため、整数かどうかの判定には一定の許容誤差（イプシロン）を設けている点が実装上の重要なポイントです。