C++로 숫자가 a^b(정수의 거듭제곱) 형태로 표현 가능한지 확인하는 방법

문제 개요

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

알고리즘

isRepresentPower(num):
시작
    if num == 1이면 true 반환
    i := 2부터 i² <= num까지 1씩 증가하며 반복:
        val := log(num) / log(i)
        if val의 소수 부분 < 0.0000001이면 true 반환
    반복 종료
    false 반환
끝

알고리즘 동작 원리

• 기저 조건: 1은 항상 1ⁿ(n ≥ 2)으로 표현되므로 true를 반환합니다.
• 밑(base) 탐색 범위: 지수가 최소 2 이상이려면 밑은 √num을 초과할 수 없습니다. 따라서 2부터 i² ≤ num을 만족하는 범위만 검사하면 충분합니다.
• 로그 활용: num = iᵏ가 성립한다면 k = log(num) / log(i) 입니다. 이 값이 거의 정수라면 num은 i의 거듭제곱입니다.
• 오차 허용: 부동소수점 연산에는 미세한 오차가 존재하므로, 소수 부분의 절댓값이 아주 작은 값(예: 0.0000001) 미만일 때 정수로 간주합니다.

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);
        // abs()로 소수 부분의 절댓값을 비교해 부동소수점 오차에 더 안전하게 처리
        if (abs(val - (int)val) < 0.00000001)
            return true;
    }
    return false;
}

int main() {
    int n = 125;
    cout << (isRepresentPower(n) ? "거듭제곱으로 표현 가능" : "거듭제곱으로 표현 불가능");
}

실행 결과

거듭제곱으로 표현 가능

125는 5³이므로 위 프로그램은 "거듭제곱으로 표현 가능"을 출력합니다. 반면 n = 91을 대입하면 어떤 밑에서도 로그 결과가 정수에 가까워지지 않아 "거듭제곱으로 표현 불가능"이 출력됩니다.

복잡도 분석

• 시간 복잡도: 밑 후보를 √num까지만 검사하므로 약 O(√n · log n) 수준입니다.
• 공간 복잡도: 추가 메모리 없이 상수 공간 O(1)만 사용합니다.