[파이썬] 백준 알고리즘 No.11653 소인수분해

백준 11653번 소인수분해 문제

 

225476KB, 1360MS로 해결

 

이전 포스팅 한 소수 구하기를 응용하여 풀 수 있다.

 

주어진 수를 소수의 작은 순서로 나누어 떨어지는 데 까지 나누고

마지막 남은 나머지가 소수 리스트 안에 있다면 해결

소수 리스트 안에 없다면 소인수 분해가 불가능 하다고 판단.

 

import math
n = int(input())
array = [True for i in range(n + 1)]

for i in range(2, int(math.sqrt(n)) + 1):
    if array[i]:
        j = 2
        while i * j <= n:
            array[i * j] = False
            j += 1


data = []
for i in range(2, n + 1):
    if array[i]:
        data.append(i)

while True:
    if n in data:
        print(n)
        break

    elif n == 1:
        break

    for i in range(2, n + 1):
        if n % i == 0:
            n //= i
            print(int(i))
            break