[C++] N!의 표현법

[문제]

임의의 N에 대하여 N! 은 1부터 N까지의 곱을 의미한다. 

N! 을 소인수 분해하여 각 숫자가 몇 번 사용되었는지 사용된 숫자만 작은 수부터 사용 횟수를 출력하는 프로그램이다.

 

[입력 예제]

5

 

[출력 예제]

5! = 3 1 1

 

5! = 5 × 4 × 3 × 2 × 1= 120

120을 소인수 분해하게 되면 2 × 2 × 2 × 3 × 5로, 2는 3번, 3은 1번, 5는 1번 사용되었으므로,

5! = 3 1 1이라고 출력하였다.

---

[코드]

#include <iostream>
#include <vector>

using namespace std;

int main(int argc, const char * argv[]) {
    
    int n, num, div, rest;
    
    //1
    cin >> n;
    
    vector<int> res(n+1);
    
    //2
    for(int i=2; i<=n; i++){
        //3
        num = i;
        div = 2;
        //4
        while(1){
            //5
            if(num%div==0){
                num /= div;
                res[div]++;
            }
            //6
            else div++;
			
            //7
            if(num==1) break;
        }
    }
    
    //8
    cout << n << "! = ";
    
    //9
    for(int i=2; i<=n; i++){
        if(res[i]) cout << res[i] << " ";
    }

    return 0;
}

 

[설명]

숫자를 곱한 후 나눠가며 나누어 떨어지는 숫자를 찾는 것이 아닌 2부터 N까지의 숫자를 하나하나 반복문을 통해 나누어 떨어지는 숫자를 찾는다.

1. 숫자를 입력받는다. (n)
2. for문을 통해 2부터 n이 될 때까지 i를 증가시키며 아래 내용(3~7)을 반복한다.
3. 먼저 num에 i를 넣어주고, 나누는 수로 div는 2를 넣어준다.
4. while문을 이용하여 반복하며
5. 만약 num과 div가 나누어 떨어지면 num에 몫을 넣어준 후 res[div]를 1 증가시켜준다. (해당 자리의 숫자가 사용된 것이므로 그 자리를 증가시킴)
6. num과 div가 나누어 떨어지지 않는다면 div값을 1 증가시키며 반복한다.
7. 만약 num과 div를 나누다 1이 나오게 되면 while문을 빠져나온다.
8. 'n! =' 을 먼저 출력한다.
9. 그 후 for문을 통해 res[i]에 값이 들어있다면 res[i]의 값을 출력시켜준다.

[실행결과]