[백준 문제풀이] 11653 소인수분해 (Javascript, python)

• python

# 백준 11653 소인수분해

import sys
input = sys.stdin.readline

n = int(input())

def factorization(num):

    for i in range(2, num+1):
        while (num % i == 0):
            print(i)
            num //= i

factorization(n)

간단하게 풀었다.
하지만 pypy3으로 제출해도 백준 사이트에서 채점 시간이 엄~청 오래 걸렸다.
찾아보니 에라토스테네스의 체 라는 방법으로 소수를 찾아서 소수 리스트에 저장해두고, 그것으로 소인수분해 하는 방법도 있다.

내 코드는 어쨌든 O(N)의 시간복잡도이기 때문에 시간을 많이 잡아먹고, N의 단위가 커질수록 매우 비효율적이게 되므로 다른 로직으로도 짜봐야겠다.

소수 구하기 시간복잡도