C++에서 숫자가 크리슈나무르티(Krishnamurthy) 수인지 확인하는 방법

이번 글에서는 특정 숫자가 크리슈나무르티 수(Krishnamurthy Number)인지 판별하는 방법을 알아보겠습니다. 어떤 수의 각 자릿수에 대한 팩토리얼 값을 모두 더한 합이 원래의 수와 같다면, 그 수를 크리슈나무르티 수라고 부릅니다.

예를 들어 숫자 145를 살펴보겠습니다.

1! + 4! + 5! = 1 + 24 + 120 = 145

각 자릿수의 팩토리얼 합이 145로 원래 숫자와 일치하므로, 145는 크리슈나무르티 수입니다. 이 외에도 1과 2(1! = 1, 1! + ... = 2), 그리고 40585(4! + 0! + 5! + 8! + 5! = 24 + 1 + 120 + 40320 + 120 = 40585)가 대표적인 예입니다.

판별 알고리즘

판별 로직은 매우 간단합니다.

1. 주어진 숫자의 각 자릿수를 하나씩 추출합니다.
2. 각 자릿수의 팩토리얼을 계산하여 누적합을 구합니다.
3. 누적합이 원래 숫자와 같으면 크리슈나무르티 수입니다.

C++ 구현 예제

#include <iostream>
using namespace std;

// 재귀 함수로 팩토리얼 계산
long factorial(int n){
    if(n <= 1){
        return 1;
    }
    return n * factorial(n - 1);
}

// 크리슈나무르티 수 여부 판별
bool isKrishnamurty(int number) {
    int temp = number;
    int sum = 0;
    while(number > 0){
        sum += factorial(number % 10); // 마지막 자릿수의 팩토리얼을 합산
        number /= 10;                  // 다음 자릿수로 이동
    }
    return sum == temp;
}

int main() {
    int n = 145;
    if(isKrishnamurty(n)){
        cout << n << "은(는) 크리슈나무르티 수입니다";
    } else {
        cout << n << "은(는) 크리슈나무르티 수가 아닙니다";
    }
}

실행 결과

145은(는) 크리슈나무르티 수입니다

코드 설명

factorial() 함수는 재귀 호출을 이용해 인자로 받은 정수의 팩토리얼을 반환합니다. n이 1 이하일 때는 1을 반환하여 재귀를 종료합니다.

isKrishnamurty() 함수는 원본 숫자를 temp에 저장해 둔 후, number % 10으로 마지막 자릿수를 얻어 팩토리얼을 합산하고, number /= 10으로 자릿수를 줄여가며 반복합니다. 모든 자릿수를 처리한 뒤 합계와 원본 값이 같으면 true를 반환합니다.

이 알고리즘의 시간 복잡도는 숫자의 자릿수에 비례하므로 O(d)(d는 자릿수)이며, 실용적으로 매우 효율적입니다.