백준 문제 풀이 - 에라토스테네스의 체 2960번

📜 문제 이해하기

에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다.
이 알고리즘은 다음과 같다.
2부터 N까지 모든 정수를 적는다.
아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.
P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.
아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.
N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오.

💡 문제 재정의

에라토스테네스의 체에서 K번째 지워지는 수를 구하자.

✏️ 계획 수립

에라토스테네스의 체의 알고리즘대로 지우면된다. 다만 위는 2*i부터 지우는게 아니라 i부터 지운다. 즉, 2, 3도 소수지만 지워지는 걸 감안해서 프로그래밍을 하자.

💻 계획 수행

if __name__ == '__main__':
    N, K = map(int, input().split())
    prime_list = [False, False] + [True] * (N - 1)

    cnt = 0
    for i in range(2, N + 1):
        if prime_list[i]:
            for j in range(i, N+1, i):
                if prime_list[j]:
                    prime_list[j] = False
                    cnt += 1
                    if cnt == K:
                        print(j)
                        exit(0)

🤔 회고

에라토스테네스의 체를 알고있으면 쉽게 풀 수 있다.