[인프런 C++] 27. N!의 표현법

✏️ 문제

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

이러한 큰 수를 표현하는 방법으로 소수들의 곱으로 표현하는 방법이 있다.

예를들어 825 = 0 1 2 0 1 로 표현가능한데, 이는 2는 없고, 3은 1번, 5는 2번, 7은 없고, 11은 1번의 곱이라는 의미이다. 

이와 같이 변환하는 프로그램을 작성해보자.

 

🍧 입력

5

 

🎭 출력

5! = 3 1 1

 

✨ 1트 (강의 풀이)

소수를 배열로 만들지, 만든다면 입력된 n까지의 소수의 갯수만큼 만들어야할지? 또 그렇다면, 그 만큼 소수판별기를 굴려서 해야하는데 이게 효율적이지 않은 것 같음. n까지의 모든수를 배열로 만드는 것 같진 않음. 소수만 카운팅해야하니까. 어떻게 풀어야할지 판단이 안서서 강의풀이를 보기로 하였다.

강의풀이 👉 배열을 만드는 것 맞음. n까지의 값들 모두. 단, 2부터 소인수분해 겸 배열의 해당 요소에 ++를 해준다. 만약, 8과 같은 수가 있다면, 8/2 = 4인데, 바로 3으로 나눠주는 것이 아니라, 2로 나눌 수 있을 때까지 계속해서 나눠준다는 것이 포인트. 그러다가 해당값이 1이 될 때 while문 탈출

#include <iostream>
#include <vector>
#include<algorithm>
using namespace std;

int main(void){
	//freopen("input.txt", "rt", stdin);
	
	int n, tmp, j;
	cin >> n;
	vector<int> a(n+1);
	
	for(int i = 2; i <= n; ++i){
		tmp = i;
		j = 2;
		
		while(true){
			if(tmp % j == 0){
				tmp = tmp / j;
				a[j]++;
			}
			else{
				j++;
			}
			
			if(tmp == 1) break;
		}
	}
	
	cout << n << "! = ";
	for(int i = 2; i <=n; ++i){
		if(a[i] != 0){
			cout << a[i] << ' ';
		}
	}
	 
	
	return 0;
}