[소인수분해] 11653. 소인수분해

1. 문제 해결 전략

너무 어렵게 갔다.. 정석을 따라서 에라토스테네스의 체로 소수를 전부 담았다가 가장 적은 소수부터 N을 나누어갔는데 그럴 필요가 없었다. 필요한건 소수의 집합이 아니라 소수로 나누어지는지였고 일부러 N의 크기를 10,000,000 이하로 두어서 배열을 쓰는순간 탈락이 되어버리는 상황이었다.

 

----

다시 보니까 이건 그냥 소수랑 아무관련이 없다. 물론 소인수들은 전부 소수지만.. i=2부터 나누어가면 소수로 나누든 소수가 아닌수로 나누듯 딱히 의미가 없다 ㅜ 그냥 %연산하면 끝나는문제였구나..

 

#include <iostream>
#include <vector>
#include <math.h>
using namespace std;

int main()
{
	int n;
	cin >> n;

	for (int i = 2; i <= sqrt(n); i++)
	{
		while (n%i == 0)
		{
			printf("%d\n", i);
			n /= i;
		}
	}

	if (n != 1)printf("%d\n", n);

	return 0;
	// 소인수들은 소수여야함. 수가 소수로 나뉘어지는지
}

algorithm 라이브러리에 존재하는 sort함수를 사용하여 오름차순으로 정렬해준다.

그 외에 특별할 것 없는 문제이다.

 

2. 걸린 시간

실패

 

3. 느낀점

너무 저번문제에 얽매인듯.

 

4. 링크

https://www.acmicpc.net/problem/11653