소인수분해

11653번: 소인수분해

🤔생각해보기

1. n을 i 로 나눠보고 나머지가 0 이라면 출력, n //= i 를 사용하여 n을 몫으로 재설정
2. n이 i로 나누어지지 않는다면 i += 1
3. i^2가 n과 같아질 때까지 실행

만약 n = 10이라면, 2 로 나누어지고 n = 5 가 된다. 5는 소수이므로 i는 증가만 하다가 5가 되면서 루프를 빠져나오게 되고 결과가 2와 5만 출력되게 된다.

5는 소수이므로 ⇒ 소수를 판별하는 과정은 제곱근을 활용한다. 자세히 생각해보니 i와 n이 같아질 때까지 검사하는 것은 시간복잡도만 증가시킬 것 같았다.

애초에 루프를 i의 제곱이 n과 같아질 때까지만 실행시키면 된다.

 

성공 코드

n = int(input())

i = 2
while i ** 2 <= n:  # 굳이 n까지 갈 필요없이 i의 제곱까지만 검사해도 된다.
    if n % i == 0:
        print(i)
        n //= i
    else:
        i += 1

if n != 1:
    print(n)