[백준 11653] 소인수 분해 python

문제

풀이

통과된 풀이

• 가장 작은 수부터 시작
• 나누어 떨어지지 않을 때 까지 그 수로 나누어주면 그 수의 배수는 앞으로 체크안될테니까 소수로만 나누어짐

N = int(input())
m = 2 # 1은 소수가 아니니까 2부터 시작
while N != 1: 
    if N % m == 0:
        print(m)
        N = N // m
    else:
        m += 1

시간 초과 풀이

• n보다 작은 수 중 가장 작은 소수를 찾아서 계속 나누어주는 방법
•  error를 두어 소수가 아닌 경우 체크

n = int(input()) # 소인수 분해할 변수
num = 1 # 소수를 저장할 변수
# n보다 작은 수 중 가장 작은 소수부터 찾아 나가기
while n >= num: # num보다 n이 커지면 루프 종료
    num += 1 # 1은 소수가 아니니까 2부터 시작
    error = 0 # 소수가 아닐 경우를 판별하기 위해 error
    for i in range(2, num): # 2부터 num보다 작은수로 
        if num % i == 0: # num이 나누어지면
            error += 1 # 소수가 아닌거니까 error증가
            break # 멈추기
    if error == 0: # error가 없다 = 소수이다
        while True: 
            remain = n % num # 찾은 소수로 n이 나누어지는지 확인
            if not remain: # 나누어 지면
                n = n // num # 소인수분해 반복
                print(num)
            else:
                break # 안 나누어지면 멈추기