[백준 15965] K번째 소수 (python)

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

15965번: K번째 소수

K번째 소수 문제

K번째 소수를 출력하는 문제, 에라토스테네스의 체를 이용해서 소수를 구하고, k번째 소수를 구해보자

에라토스테네스의 체 개념만 알면 어렵지 않게 풀 수 있다.

📌 문제 접근 포인트

1. K번째 소수를 구하는 알고리즘을 짜야하는데, K의 최대 요구사항이 40000인점을 생각해야한다.
2. 40000번째 소수까지 구해주려면 40000번째 소수가 약 700만이 넘어가는 숫자이기에, 어느정도 되는 수까지 소수를 먼저 구해줄 필요가 있다.
3. 에라토스테네스의 체로 소수를 구하면 빠르게 연산해서 구해줄 수 있다.
4. 요구사항대로  출력하면 끝

⚙ 내가 푼 정답 코드

import sys
N = int(sys.stdin.readline())
M = 7400000
array = [0]*(M+1)
for i in range(2, int(M**0.5)+1):
    if array[i] == 0:
        for j in range(i*i,M+1,i):
            array[j] = 1
x = [i for i in range(2,M+1) if array[i] == 0]
print(x[N-1])