사용자 도구

사이트 도구


ps:problems:boj:31216

슈퍼 소수

ps
링크acmicpc.net/…
출처BOJ
문제 번호31216
문제명슈퍼 소수
레벨실버 5
분류

소수 목록

시간복잡도O(nlog^2(n) + q)
인풋사이즈n<=3000, q<=1000
사용한 언어Python 3.11
제출기록35096KB / 48ms
최고기록48ms
해결날짜2024/01/08

풀이

  • k번째 소수를 p[k] 라고 쓸때, k가 소수이면 슈퍼소수가 된다. 즉, k번째 슈퍼소수는 p[p[k]] 이다.
  • 예제에 친절하게 3000번째 슈퍼소수가 318137이라고 나와 있으므로, 처음에 318137까지의 소수 목록을 구해 놓으면, 각 쿼리를 O(1)에 처리할수 있다.
  • 일반적인 n의 범위에 대해서 시간복잡도를 구한다면, 먼저 {{n번째 소수}번째 소수}까지의 범위에 대해서 소수 목록을 구해야 할텐데, 소수정리에 따라 n번째 소수를 nlogn이라고 생각하면한다면, 체를 돌려야하는 범위는 대략 nlog^2(n)이 될것이다.

코드

"""Solution code for "BOJ 31216. 슈퍼 소수".

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

Tags: [sieve]
"""

import sys
from teflib import numtheory

MAX = 318_137


def main():
    T = int(sys.stdin.readline())
    primes = numtheory.prime_list(MAX)
    for _ in range(T):
        n = int(sys.stdin.readline())
        print(primes[primes[n - 1] - 1])


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
S A S D O
 
ps/problems/boj/31216.txt · 마지막으로 수정됨: 2024/01/08 08:24 저자 teferi