[it 취업을 위한 알고리즘 문제풀이 (with C/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)이 입력된다.

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

💡 입력예제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

 

---

코드

최종 풀이

#include <stdio.h>
#include <vector>

using namespace std;

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

 

---

설명

사용자로부터 N을 입력받고 2~N까지 반복하는 for문을 작성한다.(1은 소수가 아니므로)

각 자연수를 기준으로 소인수분해하여 나온 소수들을 배열 ch의 index에 해당하는 값에 conting한다.

따라서 for문을 돌 때 마다 tmp와 j를 i와 2로 초기화해놓고 무한루프를 통해 tmp가 1이될 때까지 j로 나누어 0으로 떨어질 경우 해당 j를 index로 하는 ch배열의 값을 1씩 증가하고 tmp를 j로 나눈 값으로 갱신시킨다. 또한 0이 아닌 경우 j를 증가해 다음 소수를 찾아 나간다.

만약 tmp가 1이면 소인수분해가 끝난 것을 의미하므로 break를 통해 무한루프를 빠져나온다.

마지막으로 ch배열에서 값이 0인 경우를 제외하고 나머지 값을 출력하여 마무리한다.

 

---

배운 점

소인수분해란 소인수들의 곱으로 이루어져 있으며 각 소인수들은 소수로 이루어진다.

 

---

 

해당 내용은 김태원님의 'it 취업을 위한 알고리즘 문제풀이' 강의를 듣고 작성한 글입니다.