C++에서 n 이하의 모든 팩토리얼 수를 찾는 방법

이 글에서는 n보다 작거나 같은 모든 팩토리얼 수(계승 수)를 출력하는 방법을 알아보겠습니다. 어떤 수 N이 양의 정수의 계승(팩토리얼)으로 표현될 수 있다면, 그 수를 팩토리얼 수라고 부릅니다. 예를 들어 1, 2, 6, 24, 120 등이 팩토리얼 수에 해당합니다.

접근 방법

팩토리얼 수를 구하기 위해 매번 팩토리얼을 직접 계산할 필요는 없습니다. 더 효율적인 방법은 i = 1부터 시작하여 이전 팩토리얼 값에 i를 곱해 나가는 것입니다. 초기 팩토리얼 값은 1로 설정하고, 계산된 값이 n 이하인 동안 출력을 반복하면 됩니다.

이 방식은 각 단계마다 곱셈 한 번만 수행하면 되므로, 처음부터 팩토리얼을 새로 계산하는 것보다 훨씬 간단하고 효율적입니다. 코드를 통해 자세히 살펴보겠습니다.

예제 코드

#include <iostream>
using namespace std;

void getFactorialNumbers(int n) {
    int fact = 1;   // 초기 팩토리얼 값 (0! = 1)
    int i = 2;      // 다음에 곱할 숫자

    while(fact <= n){
        cout << fact << " ";
        fact = fact * i;   // 이전 팩토리얼에 i를 곱함
        i++;
    }
}

int main() {
    int n = 150;
    getFactorialNumbers(n);
}

출력 결과

1 2 6 24 120

동작 원리

위 코드의 실행 과정을 단계별로 살펴보면 다음과 같습니다.

처음 fact가 1이므로 1을 출력한 뒤, fact에 2를 곱해 2가 됩니다. 다음으로 2를 출력하고 3을 곱해 6이 되며, 이어서 4를 곱해 24, 5를 곱해 120이 됩니다. 마지막으로 6을 곱하면 720이 되어 n(150)보다 커지므로 반복문이 종료됩니다.

시간 복잡도

이 알고리즘의 시간 복잡도는 O(log n)입니다. 팩토리얼은 지수적으로 증가하기 때문에 n 이하인 팩토리얼 수의 개수는 전체 크기 n에 비해 매우 적습니다. 따라서 반복 횟수 역시 매우 제한적이며, 공간 복잡도는 추가 변수만 사용하므로 O(1)입니다.