[알고리즘 연습] N!의 표현법 (feat. 소인수분해) (by. C++)

N!의 표현법

• 정수 N을 입력 받는다. (N>=2)
• N!을 소인수 분해하고 이를 N! = a b c d ...의 형태로 표현하라.
• a b c d는 모두 소수로 작은 숫자부터 차례대로 표현한다. N보다 작은 소수만 표기하면 된다. (5! = 3 1 1 이면 소수 2가 3개, 소수 3이 1개, 소수 5가 1개로 소인수 분해된다는 뜻)

---

풀이

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

int main() {
​​​​int i, j, n, tmp;

​​​​cin >> n;
​​​​vector<int> ch(n+1); 

​​​​for (i=2; i<=n; i++) {
​​​​​​​​tmp=i;
​​​​​​​​j=2;
​​​​​​​​while (tmp != 1) {
​​​​​​​​​​​​​if (tmp % j == 0) {
​​​​​​​​​​​​​​​​​tmp = tmp / j;
​​​​​​​​​​​​​​​​​ch[j] += 1;
​​​​​​​​​​​​} else {
​​​​​​​​​​​​​​​​j += 1;
​​​​​​​​​​​​}
​​​​​​​​}
​​​​}

​​​​cout << n << "! = ";
​​​​for (i=2; i<=n; i++) {
​​​​​​​​if (ch[i] != 0) {
​​​​​​​​​​​​cout << ch[i] << " ";
​​​​​​​​}
​​​​}        

​​​​return 0;
}

• 소인수분해의 원리를 잘 이해하고 있어야 쉽게 풀리는 문제이다.
• 특정수를 소인수분해할때는 2부터 특정수를 계속 나눈다. 단, 0으로 나누어떨어지지 않게되면 1을 더해 나눈다. 소수가 아닌 수는 이미 앞선 소수에서 소인수분해 되었기 때문에 자연스럽게 넘어가게 된다.
• 이러한 소인수분해의 원리로 각 소수가 몇개씩 존재하는지 체크해 배열 ch에 기록한다.
• N!이기 때문에 N보다 작은 소수라면 최소 1개가 체크된다. 따라서 0이라면 소수가 아니다.