[Coding test Basic with c++] 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)이 입력된다.

▣ 출력설명
소수의 곱으로 표현한다.

 

입력 예제

5

 

출력 예제

5! = 3 1 1

 

풀이

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;

int main() {
	int n, i, j, tmp;
	
	scanf("%d", &n);
	vector<int> a(n+1);
	
	for(i=2; i<=n; i++){
		tmp=i;
		j=2;
		while(1){
			if(tmp%j==0){
				tmp=tmp/j;
				ch[j]++;
			}else j++;
			if(tmp==1) break;
		}
	}
	
	printf("%d! = ", n);
	for(i=2; i<n; i++){
		if(ch[i]!=0) printf("%d ",ch[i]);
	}

	return 0; 

}

N!=1 * 2 * 3 ... * N 이면 1을 제외하고 2부터 나누어 나머지가 0이 되면, 소인수분해가 된다. 나누어 떨어진 값을 ch 배열에 횟수를 저장하고 값이 1이 될때까지 나눈다. ch 배열에 저장된 값을 n개 만큼 출력해주면 된다.