[백준] 20946. 합성인수분해

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

문제요약

• 수를 합성수로 인수분해(${10^{12}}$)
• 여러가지 경우가 나오면 사전순으로 가장 앞서는 것(문제 조건 참고)
  • 길이가 짧다고 무조건 앞서는건 아니고
  • 왼쪽부터 비교하다가 처음으로 틀리는 지점이 앞서거나
  • 처음으로 틀리는 지점이 없는데 길이가 짧거나

접근법

• 소수를 구하고 (${10^6}$까지 구함)
• n을 인수분해해서 작은 소수부터 나열
• 소수면 => -1
• 앞에서부터 두개씩 묶어서 곱하고 출력
  • 앞에서부터 작아야 이득임
• 전체 인수 개수가 홀수면, 가장 끝은 3개로 묶음
  • 홀수면 가장 끝 값을 그 이전값에 곱해서 전체 개수를 짝수로 만들고 작업함