Stage_9 (기본수학2) 11653번 소인수분해

www.acmicpc.net/problem/11653

11653번: 소인수분해

#백준's Stage9 (기본수학) 11653번 소인수분해

# N이 주어짐 1<= N <= 10,000,000 자연수

# 각 줄의 소인수분해 값을 오름차순으로 출력

 

N = int(input())

m = 2

 

#2부터 나누고 나눈 값이 1이 될때까지 반복

while N != 1:

  if N % m == 0:

    N = N / m

    print(m)

  else: m += 1

 

 

## comments : 아래 처럼 소인수들을 List에 저장하여 출력하는 코드를 작성하였는데, 시간초과....

                    리스트로 저장할 경우 시간이 오래걸렸던 것으로 판단된다. 또는 함수를 호출하는데 오래걸렸거나

                    

 

#한 숫자로 나눌 수 있을 떄가지 반복해서 나누는 함수

 

def factorization (N,n):

  prime_list =[]

  for i in range(N):

    if N % n == 0:

      N = N / n

      prime_list.append(n)

    elif N % n != 0: break

  return int(N), prime_list

 

N = int(input())

 

prime_nos = []

 

for i in range(2,N+1):

  temp_N, temp_list = factorization(N, i)

  prime_nos += temp_list

  N = temp_N

 

for j in prime_nos: print(j)

 

## 시간초과