[ 백준 ] 2960 에라토스테네스의 체 (python)

 

 

 

 

 

 

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

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

 

 

🔥 문제 풀이

 

문제를 읽고 에라토스테네스 체를 사용해서 최대 범위인 1000까지 소수를 구해놓고, 그 소수들의 순서가 k - 1번째 일 때 값을 출력하면 되겠다고 생각했다.( 리스트는 0부터 시작하므로 k -1번째 값을 출력해야 우리가 원하는 답을 찾을 수 있음 )

 

그래서 늘 풀어왔던 방법대로 소수인지 확인하는 범위를  int(math.sqrt(n)) + 1 로 잡아서 소수를 모두 리스트에 담아서 문제를 풀었더니 틀림..😱 두 번째 예제에서 원하는 값이 나오지 않았다😥

( 👀 에라토스테네스의 체에 대한 기본 설명은 여기서 [ 백준 ] 1929 소수 구하기 - 에라토스테네스의 체 ) 

 

어떤 게 문제인지 살펴보니 범위 설정 때문에 int(math.sqrt(n)) + 1보다 큰 숫자는 소수 리스트에 담기지 않아서len(소수 리스트) < k 가 되어버린 것이다! 이렇게 되면 k - 1번째 값을 구할 수 없는 게 당연함🤦‍♀️

 

따라서 제곱근을 사용한 범위말고, 그냥 주어진 n  + 1까지의 숫자들을 모두 확인해서 소수를 뽑아내는 방법을 택했더니 문제없이 통과를 했다.

 

 

앞으로 무조건 알고있는 방법으로 풀어내지 말고, 범위나 조건을 잘 확인해야겠다😅

 

 

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