문제 링크 -> https://www.acmicpc.net/problem/2960

---

1. 문제

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

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

2부터 N까지 모든 정수를 적는다.
아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.
P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.
아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.
N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오.

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

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

---

2. 접근

처음에는 2부터 n까지의 수를 담은 배열을 만들어서 직접 에라토스테네스의 체를 구현시키려고 했다. 하지만 코드가 복잡해져서 이 방법이 아니라는 것을 깨달았다.

문제에서 요구하는 것은 소수가 아니라, k 번째에 제외되는 수이다.

우선 True로 이루어진 배열을 만든다. 그리고 반복문을 돌며 i의 배수에 해당하는 인덱스를 False로 바꿔준다. 동시에 cnt를 센다. cnt가 k가 같아졌을 때, i의 배수를 돌고 있던 j를 출력한다.

---

3. 코드

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
arr = [True]*(n+1)
cnt = 0

for i in range(2, n+1):
    for j in range(i, n+1, i):
        if arr[j] != False:
            arr[j] = False
            cnt += 1
            if cnt == k:
                print(j)

---

4. 추가

에라토스테네스의 체 - 위키백과

def prime_list(n):
    # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
    sieve = [True] * n

    # n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사
    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if sieve[i] == True:           # i가 소수인 경우
            for j in range(i+i, n, i): # i이후 i의 배수들을 False 판정
                sieve[j] = False

    # 소수 목록 산출
    return [i for i in range(2, n) if sieve[i] == True]

---

알고리즘 분류

• 수학
• 구현
• 정수론
• 소수 판정
• 에라토스테네스의 체