소인수 분해 응용

임의의 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

3 1 1

 

▣ 입력예제 2

53

 

▣ 출력예제 2

49 23 12 8 4 4 3 2 2 1 1 1 1 1 1 1

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

int main()
{
	int j;
	int tmp = 0;
	int index=0;
	int N;
	cin >> N;
	vector<int> a(N+1);//동적배열 할당 

	for (int i = 2; i <= N; i++)//소인수분해
	{
		tmp = i;
		j = 2;
			while (1)
			{
				if (tmp % j == 0)//2,3,4..N까지 중 각 수마다 소인수분해 한후 나온 값들을 vector배열의 값에 맞게 1씩 증가시켜줌
				{
					tmp = tmp / j;
					a[j]++;
					
				}
				else//나눗셈이 안되면 나누는 값을 증가
					j++;

				if (tmp == 1)//나눈후 값이 1이면 break후 다음 수를 소인수분해함
				{
					break;
				}
			}
	}
	for (int i = 0; i <= N; i++)
	{
		if (a[i] != 0)
		{
			cout << a[i] << endl;
		}
		
	}
}