슈퍼 소수

• 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()

• Dependency: teflib.numtheory.prime_list