테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== 슈퍼 소수 ======

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

===== 코드 =====
<dkpr py>
"""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()

</dkpr>
  * Dependency: [[:ps:teflib:numtheory#prime_list|teflib.numtheory.prime_list]]

{{tag>BOJ ps:problems:boj:실버_5}}