[백준][Python] 11653 소인수분해

소인수분해

접근

임의의 자연수 N을 소인수분해 하기 위해서는
나누어주는 숫자 i를 2부터 1씩 증가시키며 N이 나누어떨어지는지 확인해야 한다.
i는 증가하기 때문에, 만약 i로 나누어떨어진다면, i는 N의 소인수이다.

i의 증가 범위는 가장 쉽게 생각하면 N이 될 때 까지 이다.
N이 소수인 경우 N의 소인수는 자기 자신이기 때문이다.

그러나 약수의 대칭성을 생각해본다면
N % i == 0 일때 N % (N//i) == 0 이므로,
(N//i)은 확인하지 않아도 해당 숫자가 N의 약수임을 알 수 있다.
또한 N이 두 수의 곱으로 표현 가능할 때 둘 중 하나는 $\sqrt{N}$ 이하이므로,
i가 될 수 있는 최대값을 $\sqrt{N}$ 까지 줄일 수 있다.

코드

def solution(N: int):
    answer = []
    i = 2
    while i * i <= N and N != 1:		# 1
        if N % i == 0:
            answer.append(i)
            N //= i
        else:
            i += 1
    if N > 1:							# 2
        answer.append(N)
    return answer


if __name__ == '__main__':
    import sys
    N = int(sys.stdin.readline().rstrip())
    ans = solution(N)
    print(*ans, sep='\n')

주석 1번

i의 최대값이 $\sqrt{N}$이므로,
i의 제곱이 N이하일 때 까지만 i를 증가시킨다.
또한, i가 $\sqrt{N}$이 되기 전에 N이 1이 된다면,
이미 소인수분해가 종료된 것이므로 반복문을 중단한다.

주석 2번

위의 반복문을 종료한 뒤,
아직 N이 1보다 크다면,
N은 마지막 소인수이므로, 정답 리스트에 추가한다.