C++로 팩토리얼이 x로 나누어 떨어지는 첫 번째 자연수 찾기

이 문제에서는 팩토리얼(factorial)이 주어진 수 x로 나누어 떨어지는 첫 번째 자연수를 찾아야 합니다. 사용자로부터 x 값을 입력받으며, 조건을 만족하는 가장 작은 자연수 N을 구하는 것이 목표입니다.

예를 들어 x = 16이라고 가정해 보겠습니다. 이때 정답은 6입니다. 그 이유는 6! = 720이고, 720 mod 16 = 0이기 때문입니다. 즉, 6!은 16으로 나누어 떨어지며, 그보다 작은 수의 팩토리얼(1! ~ 5!)은 16으로 나누어 떨어지지 않습니다.

접근 방법

가장 일반적인 방법은 다음과 같습니다.

1부터 시작하여 1!, 2!, 3!, … , n!을 차례대로 계산합니다.
각 단계마다 현재 팩토리얼 값을 x로 나눈 나머지(modulus)를 확인합니다.
나머지가 0이 되는 순간 반복을 멈추고 해당 숫자를 반환합니다.

C++ 구현 예제

#include<iostream>
using namespace std;
int getNumber(int x) {
    int fact = 1;
    int i = 0;
    while(fact % x != 0){
        i++;
        fact = fact * i;
    }
    return i;
}
int main() {
    int x = 16;
    cout << "Minimum value of N is: " << getNumber(x);
}

실행 결과

Minimum value of N is: 6

코드 동작 원리

getNumber 함수는 변수 fact에 누적 곱을 저장하면서 팩토리얼을 계산합니다. while 루프는 fact % x의 결과가 0이 아닌 동안 계속 실행되며, 매 반복마다 i를 1씩 증가시키고 fact에 i를 곱해 새로운 팩토리얼 값을 만듭니다. fact % x == 0이 되는 순간 루프가 종료되고, 조건을 만족하는 첫 번째 자연수 i가 반환됩니다.

x = 16인 경우의 진행 과정을 살펴보면 다음과 같습니다.

1! = 1 → 1 % 16 ≠ 0
2! = 2 → 2 % 16 ≠ 0
3! = 6 → 6 % 16 ≠ 0
4! = 24 → 24 % 16 ≠ 0
5! = 120 → 120 % 16 ≠ 0
6! = 720 → 720 % 16 = 0 ✓

따라서 함수는 6을 반환하게 됩니다.

참고 사항

이 방법은 직관적이고 구현이 간단하지만, x가 큰 값일 경우 팩토리얼이 매우 빠르게 증가하여 int 타입의 범위(약 21억)를 초과할 수 있습니다. 실제 환경에서는 long long 타입을 사용하거나, 소인수분해 기반으로 x의 약수 조건을 만족하는 최소 n을 찾는 방식으로 개선할 수 있습니다.