[백준] 11653 - 소인수분해

www.acmicpc.net/problem/11653

11653번: 소인수분해

• 2가지 방법으로 풀 수 있고 각 방법 마다 실행 속도가 차이난다.
• 처음에 보자말자 가장 간단하게 for() 를 사용한 코드를 구현했고 32ms가 나왔다.
• 채점 결과에 확인해보니 더 빠른 결과들이 있어 다시 고민하였다.
• sqrt()를 활용하면 더 빠른 수행속도를 기대할 수 있었다.

 

---

• for() 사용

#include <iostream>
#include <vector>

#define MAX_NUM 10000001

int main()
{
	// init
	std::ios::sync_with_stdio(false);

	// input
	int N = 0;
	(void)scanf("%d", &N);
	
	// calc
	if (1 == N)
		return 0;
	
	std::vector<int> resultList;
	int diviedNum = 2;
	while (true)
	{
		if (1 == N)
		{
			break;
		}
		else if (0 == N % diviedNum)
		{
			N /= diviedNum;
			resultList.push_back(diviedNum);
			diviedNum = 2;
		}
		else
		{
			diviedNum++;
		}
	}


	for(int item : resultList)
	{
		printf("%d\n", item);
	}

	return 0;
}

• sqrt() 사용

#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>

#define MAX_NUM 10000001

void calcSqrtN(const int N, std::vector<int>& dest)
{
	int sqrtN = sqrt(N);
	if (1 == sqrtN)
	{
		if(1 != N)
			dest.push_back(N);

		return;
	}
	else
	{
		int diviedN = N / (int)sqrtN;
		while (true)
		{
			if (N == sqrtN * diviedN)
			{
				if (1 == sqrtN)
				{
					dest.push_back(N);
				}
				break;
			}
			else
			{
				sqrtN--;
				diviedN = N / (int)sqrtN;
			}
		}

		calcSqrtN(sqrtN, dest);
		if(N != diviedN)
			calcSqrtN(diviedN, dest);
	}
}

int main()
{
	// init
	std::ios::sync_with_stdio(false);

	// input
	int N = 0;
	(void)scanf("%d", &N);
	
	// calc
	if (1 == N)
		return 0;
	
	std::vector<int> resultList;
	calcSqrtN(N, resultList);

	// print
	std::sort(resultList.begin(), resultList.end());
	for(int item : resultList)
	{
		printf("%d\n", item);
	}

	return 0;
}