백준 2960번(Python) : 에라토스테네스의 체

www.acmicpc.net/problem/2960

2960번: 에라토스테네스의 체

---

[풀이]

 

숫자가 2부터 n까지 리스트에 들어가기 때문에 따로 리스트에 숫자를 넣지 않아도 됩니다. 대신 False로 리스트를 만들어 이 숫자를 제거 했는지 확인할 수 있게 만들었습니다. 이후 반복문으로 배수를 돌며 False 리스트를 True로 변경해주면 됩니다. 이때 만약 count 가 k가 된다면 답을 출력하면 됩니다.

 

---

 

[코드]

 

import sys
input = sys.stdin.readline

n,k = map(int,input().split())
arr = [False] * (n+1)
count = 0
for i in range(2,n+1):
    for j in range(i,n+1,i):
        if arr[j] == False:
            arr[j] = True
            count += 1
            if count == k:
                print(j)
                break