[Algorithm] 백준_11653번: 소인수분해

오늘의 문제는 🚀 백준 11653 소인수분해이다.

내일 시험이 있어서 약간 쉬운 문제를 선택하게 되었다!

처음에 보자마자 에라토스테네스의 체로 풀어야 하나 했지만, 더 복잡해 질거 같아서 while문으로 해결했다!

테스트케이스 이해하기

예제처럼, 우리가 수학시간에 구했던 소인수분해를 프린트 해주면 된다!

알고리즘

1. i를 2로 두고 input값보다 작을 동안 계속 while문을 돌도록 한다.
2. i가 n을 나머지 없이 나눌 수 있는 경우, n를 나누어주고 결과값을 append 해준다.
3. 그리고 같은 숫자로 계속 다시 나누어 질 수 있기 때문에(ex. 2) continue로 다시 while를 실행시킨다.
4. i가 n을 나머지 없이 나눌 수 없는 경우는 i를 1씩 증가한다.
5. n이 1이 되면 break로 while문을 탈출한다.

정답코드

n=int(input())
i=2
result=[]
while i < n+1:
    
    if n ==1:
        break

    if n%i == 0:
        n=n//i
        result.append(i)
        continue

    i += 1

for i in range(len(result)):
    print(result[i])

🚀Reference: 백준 11653 소인수분해