[C++/inflearn 코딩테스트] N!의 표현법 (소인수 분해 응용)

C++ 온라인 컴파일러 사이트

1. https://replit.com/~
2. https://www.onlinegdb.com/online_c++_compiler
3. https://cpp.sh/
4. https://www.tutorialspoint.com/compile_cpp_online.php

#include<fstream>
#include<iostream>
#include<map>
#include<string>
#include<algorithm>
#include<vector>
#include<math.h>

using namespace std;

bool prime(int num)
{
	bool bprime = true;
	for (int i = 2; i < num ; i++)
	{
		if (num % i == 0)
		{
			bprime = false;
			break;
		}
	}
	return bprime;
}


int main() {
	ios_base::sync_with_stdio(false);
	ifstream cin;
	//ofstream cout;

	cin.open("input.txt");
	int N(0); // 명수
	int a(0); // 점수
	int i(0); // 1st index
	int j(0); // 2nd index
	map<int,int> pdic; // 소수인수분해 배열

	cin >> N;

	for ( i = 2; i <= N; i++)
	{
		int temp = i;
		if (prime(temp))
		{
			pdic[i] += 1;
		}
		else
		{
			for ( j = 2; j <= temp; j++)
			{
				while (temp % j == 0)
				{
					pdic[j] += 1;
					temp /= j;
				}
			}
		}
	}
	
	cout << N << "! = ";
	for(auto e:pdic)
	{
		cout << e.second << " ";
	}
	cout << endl;

	return 0;
}

입력

53

출력

중요한 부분

for ( i = 2; i <= N; i++)
	{
		int temp = i;
		if (prime(temp))
		{
			pdic[i] += 1;
		}
		else
		{
			for ( j = 2; j <= temp; j++)
			{
				while (temp % j == 0)
				{
					pdic[j] += 1;
					temp /= j;
				}
			}
		}
	}

int temp = i;

바로 위 코드가 중요함.

i는 while문에서 j로 계속 나눠지기에 

for문이 돌지 않게되어 무한에 빠지게 된다.