27. N!의 표현법

 

    27번 문제   

 

---

 

    내가 풀이한 답   

 문제를 읽고 소인수분해를 이용하여 풀어야겠다는 생각을 했다. 입력값의 범위가 작다보니 순회(for, while)문을 중첩해도 상관없다고 생각하고 코드를 짯다. 

 

 핵심은 소수로 표현할 때 소수의 범위는 n을 넘지 않는 다는 것이다. 따라서, n크기의 배열을 생성하여 각각의 수들을 소인수분해 하고 해당 배열의 인덱스를 증가시켜주는 방법이다. 

 

 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(int argc, char** argv) {
	//freopen("input.txt", "rt", stdin);
	int n, i, j, temp;
	scanf("%d", &n);
	
	int *arr = (int *)malloc(sizeof(int) * (n+1));
	memset(arr, 0, sizeof(int)* (n+1));
	
	for(i=2; i<=n; i++){
		temp=i, j=2;
		while(temp>1){
			if(temp%j==0){
				arr[j]++;
				temp /= j;
			}
			else j++;
		}
	}
	
	printf("%d! = ", n);
	for(i=2; i<=n; i++){
		if(arr[i] != 0) printf("%d ", arr[i]);
	}

	return 0;
}

 

 결과는 통과하였다.

 

 

---

    사이트의 답안   

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

int main(){
	//freopen("input.txt", "rt", stdin);
	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){
				ch[j]++;
				tmp=tmp/j;
			}
			else j++;
			if(tmp==1) break;
		}
	}
    
	printf("%d! = ", n);
	for(j=2; j<=n; j++){
		if(ch[j]!=0) printf("%d ", ch[j]);
	}
    
	return 0;
}
				
		

 

  사이트의 답과 똑같은 논리임을 확인하였다.