[Python] 백준 #11653 소인수분해

www.acmicpc.net/problem/11653

11653번: 소인수분해

 

#n이하의 소수들만 남기기
def func(n):
    k=0
    List=[1]*(n+1)
    List[0]=0
    List[1]=0
    result=[]
    for i in range(n+1):
        if List[i]==1:           
            for j in range(2*i,n+1,i):
                List[j]=0
    
    for i in range(2,n+1):
        if List[i]==1:
            result.append(i)
            
    return result

n=int(input())
List=func(n)

if n!=1:
    while True:
        if n==1:
            break
        for i in List:
            while True:
                if n%i!=0:
                    break
                elif n%i==0:
                    print(i)
                    n=n//i