사용자 도구

사이트 도구


ps:problems:boj:16563

어려운 소인수분해

ps
링크acmicpc.net/…
출처BOJ
문제 번호16563
문제명어려운 소인수분해
레벨골드 4
분류

정수론

시간복잡도O(n +mlogn)
인풋사이즈n<=5,000,000, m<=1,000,000
사용한 언어Python
제출기록327564KB / 3616ms
최고기록3616ms
해결날짜2022/05/28

풀이

  • 소인수분해 (Prime Factorization)에서 설명한것처럼, n이하의 모든 수에 대해서 최소인수를 계산해놓으면, n이하의 임의의 수를 O({소인수갯수}) 로 소인수분해할수 있다.
  • 모든 수의 최소인수를 계산하는 것은 에라토스테네스의 체를 변형해서 O(nloglogn)에 구할수도 있고, linear sieve를 이용해서 O(n)에 구할수도 있다. 시간복잡도는 거의 비슷하지만, 최적화를 최대한 열심히 했을때 실행 속도는 linear sieve쪽이 좀더 빨랐다.
  • 소인수의 갯수는 평균 O(logn)이다. 따라서 m개의 쿼리에 대해서 계산하는 것은 O(mlogn).

코드

"""Solution code for "BOJ 16563. 어려운 소인수분해".

- Problem link: https://www.acmicpc.net/problem/16563
- Solution link: http://www.teferi.net/ps/problems/boj/16563

Tags: [Number theory] [Linear sieve]
"""


def least_prime_factor(n):
    lpf = list(range(n + 1))
    lpf[2::2] = [2] * (n // 2)
    primes = []
    for i in range(3, n // 3 + 1, 2):
        if lpf[i] == i:
            primes.append(i)
        for p in primes:
            if i * p > n or p > lpf[i]:
                break
            lpf[i * p] = p
    return lpf


def main():
    N = int(input())  # pylint: disable=unused-variable
    k = [int(x) for x in input().split()]

    lpf = least_prime_factor(max(k))
    for k_i in k:
        answer = []
        n = k_i
        while n > 1:
            p = lpf[n]
            n //= p
            answer.append(p)
        print(*answer)


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
O K E E M
 
ps/problems/boj/16563.txt · 마지막으로 수정됨: 2022/05/28 15:57 저자 teferi