백준 15965번 : K번째 소수 [Python]

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

15965번: K번째 소수

 

 

문제 

다음은 한결이가 거울과 한 얘기중 일부이다.

• 한결 : 난 아무리 생각해도 기억력이 좋은 것 같아!
• 거울 : 양심없니?
• 한결 : 이걸 못 믿니? 너무 어이없네 ㅋㅋ
• 거울 : ㅋ ㅋ ㅋ ㅋ ㅋ ㅋ ㅋ ㅋ ㅋ ㅋ ㅋ
• 한결 : 하.. 이걸 못 믿네; 내 머릿속에 지금 모든 소수가 차례대로 들어가 있거든? 니가 원하는 번째의 소수를 대답해줄게
• 거울 : 그럼 k번째 소수가 뭔데??
• 한결 : k번째 소수는....

솔직히 한결이는 기억력이 쓰레기다. 그래서 소수를 외우고 있지 못하다. 하지만 이렇게 허세를 부리고 나니 거울한테 참교육을 시전해주고 싶었다. 한결이를 도와 k번째 소수를 알려주자.

소수의 정의는 다음과 같다.

2 이상의 자연수 N이 1과 N을 제외하고 어떤 자연수로도 나누어 떨어지지 않을 때 소수라고 한다.

 

 

입력

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

 

 

 

출력

K번째 소수를 출력하자.

 

 

예시

 

코드

import sys

num = int(sys.stdin.readline())
N_list = [1 for _ in range(10**7 + 1)]

s_list = []
for i in range(2, 10 ** 7 + 1):
    if N_list[i] == 1:
        s_list.append(i)
        for j in range(i + i, 10 ** 7 + 1, i):
            N_list[j] = 0

print(s_list[num - 1])

 

 

코드 해석

• 수를 받는다.
• N_list라는 소수인지 구별하는 용도인 리스트를 생성후 초기화해 준다.
• s_list 소수를 저장하는 리스트이다.
• for로 소수를 s_list에 넣는다.
• s_list에 num의 위치에 있는 값을 출력한다.