[210412] 27번 N!의 표현법

문제

임의의 N에 대하여 N!은 1부터 N까지의 곱을 의미한다. 이는 N이 커짐에 따라 급격하게 커진
다. 이러한 큰 수를 표현하는 방법으로 소수들의 곱으로 표현하는 방법이 있다. 먼저 소수는
2, 3, 5, 7, 11, 13... 순으로 증가함을 알아야 한다. 예를 들면 825는 (0 1 2 0 1)로 표현이
가능한데, 이는 2는 없고 3은 1번, 5는 2번, 7은 없고, 11은 1번의 곱이라는 의미이다. 101보
다 작은 임의의 N에 대하여 N 팩토리얼을 이와 같은 표기법으로 변환하는 프로그램을 작성해
보자. 출력은 아래 예제와 같이 하도록 한다.
▣ 입력설명
첫 줄에 자연수 N(3<=N<=1000)이 입력된다.
▣ 출력설명
소수의 곱으로 표현한다.

입출력

▣ 입력예제 1
5
▣ 출력예제 1
5! = 3 1 1
▣ 입력예제 2
53
▣ 출력예제 2
53! = 49 23 12 8 4 4 3 2 2 1 1 1 1 1 1 1

---

풀이

소인수 분해를 이용해서 문제를 해결할 수 있다.

n이 7이라면
1, 2, 3, 2 2, 5, 2 3, 7이므로 3 2 1 1로 표현할 수 있다.

1. 반복문을 돌면서 임시 변수 tmp에 i 값을 저장한다. 이는 i를 훼손시키면 안되기 때문이다.
2. 그다음 무한루프를 돌면서 tmp가 1이 될때까지 tmp를 j로 나눈다. j에는 가장 작은 소수인 2가 들어가며 나머지가 0이라면 tmp를 j로 나누고 배열에 ++를 한다. 나머지가 0이 아니라면 j를 ++ 한다.

코드

#include <bits/stdc++.h>
using namespace std;

int arr[1003];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n, tmp, j;

	cin >> n;

	for (int i = 2; i <= n; ++i)
	{
		tmp = i;
		j = 2;
		while (true)
		{
			if (tmp % j == 0)
			{
				tmp /= j;
				arr[j]++;
			}
			else j++;
			if (tmp == 1)
				break;
		}
	}

	cout << n << "! = ";
	for (int i = 2; i <= n; ++i)
	{
		if (arr[i] != 0)
			cout << arr[i] << ' ';
	}
}

---