michaelhyoje   8달 전

정석 풀이를 보니 로직이 제가 작성한 코드랑 완전히 달라 질문 드립니다.

hyper1423   8달 전

의도하신 건지는 모르겠지만, 올려주신 코드의 for loop가 계속 answer를 덮어쓰기 때문에 for loop가 끝날 시점에 answer는 가장 큰 두 진약수의 최소공배수가 됩니다.

어떤 자연수 $n$이 주어졌을 때, 이를 소인수분해한 꼴을

$$ n = {p_1}^{a_1} \times {p_2}^{a_2} \times {p_3}^{a_3} \times ... \quad (p_1 < p_2 < p_3 < ...) $$

이라고 해봅시다. 이 때 n의 가장 큰 진약수는 반드시

$$ {p_1}^{a_1-1} \times {p_2}^{a_2} \times {p_3}^{a_3} \times ... = \frac{n}{p_1} $$

입니다.

$n$의 어느 두 진약수의 최소공배수를 구하든 그 최소공배수는 절대 $n$을 초과할 수 없습니다. ($n$이 모든 진약수의 공배수이고, 최소공배수는 가장 작은 공배수이기 때문입니다.)

또한, 어떤 두 자연수의 최소공배수는 그 두 자연수보다 크거나 같을 수밖에 없습니다. 따라서 가장 큰 진약수 $\frac{n}{p_1}$와 임의의 진약수 $d$의 최소공배수는

$$ \frac{n}{p_1} \leq \mathrm{lcm}(\frac{n}{p_1}, d) \leq n $$

입니다. 이를 만족하는 $ \mathrm{lcm}(\frac{n}{p_1}, d) $은 $n$과 $\frac{n}{p_1}$밖에 없습니다. 전자는 그 자체로 답이 되고, 후자는 이후에 적으신 if문으로 처리됩니다. (가장 작은 진약수는 $p_1$이므로 $ \frac{n}{p_1} \times p_1 = n $입니다.)

올려주신 코드에서는 $d$를 두 번째로 큰 진약수로 잡고 있지만 $d$가 무엇이어도 상관 없습니다.

댓글을 작성하려면 로그인해야 합니다.