백준 14232번 파이썬 문제풀이(보석 도둑)

---

이 문제는 간단히 10^12 까지 소인수 분해를 할 수 있냐를 묻는 문제이다. 그러나 O(N)으로는 못돈다. 따라서 최적화된 소인수 분해 코드를 짜야하는데 O(logN) 으로 구할 수 있는 소인수 분해 식이 있다.

 

예를들어 어떤 n의 소인수 분해는

a*b*c*d*e*f*g*h*i => n

다음과 같이 표현이 가능하다. 여기서 중요한 점은 a~i 까지의 수중에 sqrt(N)보다 큰 수는 많아봐야 1개(i) 이거나 없다.(제곱수 일때) 따라서 이러한 점을 이용해서 식을 짜면 된다.

K = int(input())


# 소인수 분해 최적화(logN)
def prime(k):
    x = k
    arr = []
    for i in range(2, k):
        if i * i > k:
            break

        while x % i == 0:
            arr.append(i)
            x //= i
    if x != 1:  # 만약 제곱수가 아니라면
        arr.append(x)  # 마지막 남은 수를 추가해준다.
    return arr


arr = prime(K)
print(len(arr))
print(*arr)