[백준] 11653번 소인수분해 - 파이썬(Python)

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

11653번: 소인수분해

 

문제

 

접근법

 

소인수분해된 값들은 소수들로 이루어져있으니 소수들을 먼저 구해야한다 생각함.

때문에 입력받은 수까지의 소수를 구해서 소수 2부터 시작해서 입력받은 수가 1이 될 때까지 나눠지는 소수들을 순서대로 출력

(2로 나눴을 때 나머지가 0이 나오면 계속 2로 나누다 0이 아니면 다음 소수인 3으로 넘어가기)

 

입력받은 수가 1이면 바로 종료

 

 

코드

n=int(input())

if n==1:
    exit()

    
prime=[True]*(n+1)

prime[1]=False

for i in range(2,int(n**0.5)+1):
    if prime[i]==True:
        for j in range(i+i,n+1,i):
            prime[j]=False

loca=2

while n!=1:
    if n%loca==0:
        n//=loca
        print(loca)
    else:
        loca+=1