[Python] 31216번 슈퍼 소수

https://www.acmicpc.net/problem/31216

31216번: 슈퍼 소수

---

 

24/01/08

 

 

간단한 소수 판정 응용 문제다.

---

 

문제 접근 방식:

 

 

문제는 매우 간단하다.

 

소수를 오름 차순으로 나열하여 $k$번째 소수가 있을 때, 이 $k$가 소수라면 그 소수를 슈퍼 소수라고 한다.

 

우리의 목적은 $n$이 주어지면 $n$번째 슈퍼 소수를 찾는 것이 우리의 목적이다.

 

여기서 주어지는 $n$은 최대 $3,000$까지이다.

 

$100$만 이하의 소수의 개수는 $78,498$개이므로, $3,000$개의 슈퍼 소수를 찾는 일은 충분할 것이라고 생각되어, $100$만 이하의 소수를 에라토스테네스의 체로 먼저 구하였다.

 

이후 소수가 나올 때마다, $k$번째 소수임을 따져서, 이 $k$도 소수임을 확인하였다.

 

굳이 에라토스테네스의 체를 쓰지 않아도 통과된다고는 하는데, 에테체가 그렇게 어려운 알고리즘은 아니니 그냥 에테체로 구현하는 것이 나아 보인다.

  

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더 보기를 누르면 확인할 수 있다.

# 31216번 슈퍼 소수
# 수학, 정수론, 에테체
import sys
input = sys.stdin.readline

T = int(input())
sieve = [1 for _ in range(1_000_000)]
sieve[0], sieve[1] = 0, 0
for i in range(2, 1_000):
    if sieve[i]:
        for j in range(i*i, 1_000_000, i):
            sieve[j] = 0
super_prime = []
k_th = 0
for i in range(1_000_000):
    if sieve[i]:
        k_th += 1
        if sieve[k_th]:
            super_prime.append(i)
for _ in range(T):
    print(super_prime[int(input())-1])