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


풀이

void solve()
{
	int n;
	cin >> n;

	vector<int> cache(n + 1);

	int temp, j;
	for (int i = 2; i <= n; ++i)
	{
		temp = i;
		j = 2;
		while (true)
		{
			if (temp == 1) 
				break;

			if (temp % j == 0)
			{
				temp = temp / j;
				cache[j]++;
			}
			else
				j++;
		}
	}

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

전체 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>

using namespace std;

void solve()
{
	int n;
	cin >> n;

	vector<int> cache(n + 1);

	int temp, j;
	for (int i = 2; i <= n; ++i)
	{
		temp = i;
		j = 2;
		while (true)
		{
			if (temp == 1) 
				break;

			if (temp % j == 0)
			{
				temp = temp / j;
				cache[j]++;
			}
			else
				j++;
		}
	}

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

int main() 
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//freopen("input.txt", "rt", stdin);

	solve();

	return 0;
}

참고