C++에서 숫자가 x^y(x의 y거듭제곱) 형태로 표현 가능한지 확인하는 방법

이번 글에서는 주어진 숫자가 x^y(x의 y거듭제곱) 형태로 표현될 수 있는지 확인하는 방법을 살펴보겠습니다. 예를 들어 125는 5³으로 표현할 수 있지만, 91은 어떤 정수의 거듭제곱으로도 나타낼 수 없습니다.

핵심 아이디어는 로그 함수를 활용하는 것입니다. num = i^k가 성립하는지 확인하려면 k = log(num) / log(i)를 계산한 뒤, 이 값이 정수에 가까운지 검사하면 됩니다.

알고리즘

isRepresentPower(num):
시작
    만약 num = 1이면 true 반환
    i := 2부터 시작하여 i * i <= num인 동안 i를 1씩 증가시키며 반복:
        val := log(num) / log(i)
        만약 val - int(val) < 0.0000000001이면 true 반환
    반복 종료
    false 반환
끝

알고리즘 동작 원리

• 기저 사례: 1은 모든 지수 n에 대해 1ⁿ = 1이 성립하므로 항상 거듭제곱으로 표현할 수 있습니다.
• 로그 활용: 밑을 i로 할 때 num의 로그값(log(num) / log(i))이 정수라면, num은 i의 정수 거듭제곱입니다.
• 부동소수점 오차 처리: 실수 연산 특성상 값이 완전히 일치하지 않을 수 있으므로, 소수 부분이 0.0000000001 미만이면 정수로 간주합니다.
• 반복 범위: i² > num이 되는 시점부터는 유효한 밑이 존재하지 않으므로 탐색을 종료합니다.

C++ 구현 예제

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

bool isRepresentPower(int num) {
    // 1은 항상 거듭제곱으로 표현 가능
    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) ? "표현할 수 있습니다" : "표현할 수 없습니다");
}

실행 결과

표현할 수 있습니다

125 = 5³이므로 거듭제곱 형태로 표현할 수 있다는 결과가 출력됩니다. 반면 91을 입력하면 "표현할 수 없습니다"가 출력됩니다.

주의 사항

부동소수점 연산의 한계로 인해 매우 큰 숫자에서는 오차가 발생할 수 있습니다. 필요에 따라 허용 오차(epsilon) 값을 조정하거나, 각 밑에 대해 거듭제곱을 직접 계산하며 비교하는 정수 기반 방식을 사용하는 것이 더 안전할 수 있습니다.