공부정리

어떤 수 n이 주어졌을 때 두가지 연산을 할 수 있다.

1. *x

2. sqrt(n) : 결과가 자연수여야 하고 sqrt(n)^2 == n이어야 함

이런 연산을 통해 만들 수 있는 가장 작은 수와 그 수에 도달하기까지 최소연산의 횟수를 출력해야 한다.

입력범위 밖의 값이긴 하지만 n=19293750 일때를 생각해 보자.

만들 수 있는 가장 작은 수를 만들어야 하고 우리가 가진 연산중 값이 작아지는 연산은 2번연산 밖에 없다.

한마디로 sqrt를 더이상 취할 수 없는 수가 우리가 원하는 가장 작은 수가 된다.

sqrt를 최대한 취한다면 result(n)은 결국 1승짜리 소수의 곱으로 나타날 것이다.

n을 소수들로 표현해보면

n = 19293750 = 2 * 3^2 * 5^5 * 7^3

이고 우리가 원하는 결과는 2*3*5*7 = 210 이 될 것이다. 저기서 더 줄일 수 있는 방법이 있는가? 없다.

그렇다면 1번 연산은 n을 sqrt취할 수 있도록 만들어 주는 값을 곱하는 역할만을 할 것이다.

또한 곱하는 수 x에는 제한이 없으므로 result = sqrt(sqrt(n*x))... 이런식으로 x를 한번만 곱한다던가 혹은

아무것도 곱하지 않고 sqrt만 취하는 형태가 될 것이다. sqrt는 지수를 절반으로 낮춰주므로 우리는

n에다가 2^7 * 3^6 * 5^3 * 7^5를 한번 곱해주고 sqrt를 3번 취해주면 될 것이다.

해법

그렇다면 우리가 할 일은 n을 구성하는 소수의 거듭제곱꼴에서 지수부분을 다 구하고

모든 지수들보다 크거나 같은 2^k 값중 가장 작은 k를 구한다.