백준 20946 - 합성인수분해 (C++)

문제 문제 링크 BOJ 20946 - 합성인수분해 문제 요약 자연수 $N$이 주어진다. 이 수의 '합성인수분해' 를 구해보자.

제한 TL : $1$ sec, ML : $1024$ MB $2 ≤ N ≤ 10^{12}$ 알고리즘 분류 수학(math) 정수론(number theory) 그리디 알고리즘(greedy) 풀이 소수로 표현하는 소인수분해가 아닌 합성인수분해라니.. 꽤 흥미로운 문제 같다.

적당한 수 몇 개를 가지고 놀아보면 알겠지만, 결국 나열되는 합성수들이 단조성을 가지려면 소인수들의 곱으로 한 쌍씩 묶어주는 것이 최적임을 알 수 있다. 단, 나열되는 소인수들은 단조 증가 하여야 한다.

이에 따라 합성인수분해가 불가능 한 경우는 소인수가 하나일 때 즉, 소수일 때가 불가능 한 경우가 되겠다. 한가지.....