(백준 15965) k번째 소수(python)

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

제15965호: 제K 소수

주어진 자연수 K. (1 ≤ K ≤ 500,000)

www.acmicpc.net

K번째 소수 문제

k번째 소수 출력 문제 소수를 구하려면 에라토스테네스의 체를 이용해 k번째 소수를 구하면 됩니다.

에라토스테네스의 체 개념만 알면 쉽게 풀 수 있습니다.

질문 액세스 포인트

1. K번째 소수를 찾는 알고리즘을 작성해야 하지만 K의 최대 요구 사항이 40000인 것을 고려하면 됩니다.


2. 4만 번째 소수 찾기 4만 번째 소수는 약 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))