백준 2960번 - 에라토스테네스의 체 / Python

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

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

문제 설명

문제

에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다.

이 알고리즘은 다음과 같다.

1. 2부터 N까지 모든 정수를 적는다.
2. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.
3. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.
4. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.

N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ K < N, max(1, K) < N ≤ 1000)

출력

첫째 줄에 K번째 지워진 수를 출력한다.

---

정답

n, k = map(int, input().split())

prime = [True] * (n + 1)  # 소수 판별
prime[0] = False
prime[1] = False

for i in range(2, n + 1):
    if prime[i]:  # 소수면 실행
        for j in range(i, n + 1, i):  # 소수의 배수 지우기
            if prime[j]:
                prime[j] = False
                k -= 1
                if k == 0:
                    print(j)
                    break
    if k == 0:
        break

 

---

풀이

n, k = map(int, input().split())

prime = [True] * (n + 1)  # 소수 판별
prime[0] = False
prime[1] = False

for i in range(2, n + 1):
    if prime[i]:  # 소수면 실행
        for j in range(i, n + 1, i):  # 소수의 배수 지우기
            if prime[j]:
                prime[j] = False
                k -= 1
                if k == 0:
                    print(j)
                    break
    if k == 0:
        break

 N번까지의 수를 에라토스테네스의 체로 걸러가면서 K번째로 거르는 수를 출력하는 문제입니다. 기본적으로 에라토스테네스의 체에 대한 개념을 알고 있어야 합니다.

 이전에 소수 관련 문제를 풀어봤다면 k를 연산하는 부분만 추가하면 해결할 수 있습니다.