[백준-파이썬] 11653: 소인수분해

TMI 일기

다음 주는 싸피 프로젝트 마지막 주이다..! 다들 프로젝트하느라고 바빠서 알고리즘 스터디를 쉬기로 했다. 그래도 오랜만에 문제를 풀고 싶어서 백준에 들어왔다. 무슨 문제를 풀까 하다가

'내가 못 푼 문제'를 눌러봤다. 내가 전에 풀다가 실패했던 문제들도 나와서 그것들을 풀어봤다.

먼저 풀 문제는 소인수 분해 문제~~

https://www.acmicpc.net/problem/11653

11653번: 소인수분해

💦1년 전에 시간초과 나온 코드

N=int(input())
# N이하 소수 찾아서 리스트 S에 넣기
S=[2,3]
for i in range(4, N+1):
    if i%2==1:
        for j in range(len(S)):
            if i % S[j] ==0: break
            else:
                if j==len(S)-1: S.append(i)

# 그 중에서 S의 소인수 찾아서 출력
M=[]
for m in S:
        if N%m==0:
            print(m)
            N=N/m
        else: continue

소인수 분해는 어떤 수를 소수인 약수로 표현하는 것이다. 그래서 일단은 그 수보다 작은 소수들을 구하려고 했던 것 같다. 그걸 S 리스트에 넣고, 어떤 수를 그 소수들로 나눠줬다. 그런데 문제는... 일단 시간도 초과하고, 정답도 안나온다. 3 => 3, 6 => 2, 3은 제대로 나온다. 그런데 72 => 2,3이 나온다. 72는 원래 2, 2, 2, 3, 3이 나와야 한다. 2나 3을 여러 번 출력해야 했지만, for m in S를 하니까 m에 2, 3이 각각 한번씩만 들어가서 한번만 출력하게 된다.

💫틀렸던 코드

N = int(input())
n = N
i = 2
while i < N:
    if n % i == 0:
        print(i)
        n //= i
    else:
        i += 1

처음에 소수를 구할 필요 없이, 이렇게 하면 자연스럽게 그 수의 소수인 약수들이 나오게 된다..!
여기에서 잘못한 것이 하나 있는데! while i<N으로 한 것이다. 그러면 3 -> 3, 7-> 7 같이 소인수 분해했을 때 본인이 소인수가 되는 경우가 문제가 된다.
아래처럼 <=을 해야 한다.

💗정답 코드

N = int(input())
n = N
i = 2
while i <= N:
    if n % i == 0:
        print(i)
        n //= i
    else:
        i += 1