27. N!의 표현법 (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★★☆☆☆

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

using namespace std;

int main()
{
	int n;
	scanf("%d", &n);
	
	vector<int> prime(n+1, 0);
	vector<int> primeCount(n+1, 0);
	
	int idx = 1;
	for(int i = 2; i <= n; i++)
	{
		bool flag = true;
		for(int j = 2; j*j <= i; j++)
		{
			if(i % j == 0)
				flag = false;
		}
		if(flag)
		{
			prime[idx] = i;
			idx++;
		}
	}
	
	for(int i = n; i >= 2; i--)
	{
		int count = 1;
		int x = i;
		while(x > 1)
		{
			if(x % prime[count] != 0)
			{
				count++;
			}
			else
			{
				primeCount[count]++;
				x /= prime[count];
			}
 		}
	}
	
	printf("%d! = ", n);
	for(int i = 1; primeCount[i] != 0; i++)
	{
		printf("%d ", primeCount[i]);
	}
		
	return 0;
}

1. 자연수 n까지의 소수 찾기

코드 과정은 아래와 같다.

 

- 소수를 저장해둘 vector<int> prime(n+1, 0) 선언 및 초기화

 

- idx는 1부터 시작할 것임

 

- 2부터 소수인지 확인을 이중 for문으로 j*j <= i, 즉 제곱근까지만 확인한다.

나누어떨어진다면 소수가 아님으로 보고 flag = false 한다. flag = true 일 경우 소수로 보고

prime[idx]에 i를 추가한다.

 

- 그 소수가 얼마나 쓰였는지 확인하기 위해 같은 크기의 vector로 primeCount를 선언하고 0으로 초기화한다.

	vector<int> prime(n+1, 0);
	vector<int> primeCount(n+1, 0);
	
	int idx = 1;
	for(int i = 2; i <= n; i++)
	{
		bool flag = true;
		for(int j = 2; j*j <= i; j++)
		{
			if(i % j == 0)
				flag = false;
		}
		if(flag)
		{
			prime[idx] = i;
			idx++;
		}
	}

 

2. 본격적으로 n!을 소수의 곱으로 표현하기

- n부터 시작하는데, n을 prime[count]로 나누었을 때 나머지가 0이라면 그 소수를 한 번 사용했다고보고 primeCount[count]++을 해준 후 n을 그 소수로 나눈다.

 

ex) n = 5, prime[count] = prime[1] = 2

5 % 2 != 0

count++ (count가 2가 됨)

 

5 > 1 이기에 반복

5 % 3 != 0 (prime[count] = prime[2] = 3)

count++ (count가 3가 됨)

 

5 > 1 이기에 반복

5 % 5 == 0 (prime[count] = prime[3] = 5)

primeCount[count] = primeCount[3]++ (5를 1번 사용했다), 5 / 5 = 1

 

1 >! 1 이기에 break;

 

위 과정을 반복한 후 primeCount의 첫 번째 원소부터 값이 0(count가 안 됨, 즉 사용하지 않음) 이 아닌 원소까지 출력한다.

for(int i = n; i >= 2; i--)
	{
		int count = 1;
		int x = i;
		while(x > 1)
		{
			if(x % prime[count] != 0)
			{
				count++;
			}
			else
			{
				primeCount[count]++;
				x /= prime[count];
			}
 		}
	}