에라토스테네스의 체 - 2960

에라토스테네스의 체

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	27858	15721	13270	57.421%

문제

에라토스테네스의 체는 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번째 지워진 수를 출력한다.

예제 입력 1

7 3

예제 출력 1

6

예제 입력 2

15 12

예제 출력 2

7

예제 입력 3

10 7

예제 출력 3

9

2, 4, 6, 8, 10, 3, 9, 5, 7 순서대로 지워진다. 7번째 지워진 수는 9이다.

---

► Idea

1. 에라토스테네스의 체를 구현한다.
   1. ** 에라토스테네스의 체: N이하의 모든 소수를 찾는 알고리즘
2. 목표는 특정 순서(K)에 지워지는 찾는 수를 찾는 것이다.

---

► Code

n, k = map(int, input().split(" "))
li = list()

# 2부터 배열 생성
for i in range(2, n + 1):
    li.append(i)

cnt = 0
for i in range(len(li)):
    if li[i] == 0: # 0이면 다음 반복으로 넘어감
        continue
        
    for j in range(i, len(li)):
        if li[j] % p == 0 and li[j] != 0:
            cnt += 1
            if cnt == k: # k번째를 카운트 했다면 종료
                print(li[j])
            li[j] = 0
            
# for loop 내에서 List 길이 줄어드므로 index 에러 발생함

---

► 시간 소요한 부분

list index out of range

for i in range(len(li)):
    if li[i] == 0:
        continue
    p = li[i]
    for j in range(i, len(li)):
        # if j == le:
        #     continue
        # if li[j] % p == 0:
        #     print("Li[j]", li[j])
        #     cnt += 1
        #     if cnt == k:
        #         print(li[j])
        #
        #     li.remove(li[j])

1. 처음에 p의 배수를 발견하면 리스트에서 해당 원소를 제거했다.
2. 근데, loop 내에서 리스트의 범위가 변경되기에 list index out of range 에러가 발생했었다.
3. 따라서 원본 리스트를 수정하지 않고, 배수를 발견하면 해당 원소를 0으로 바꿨다. 그리고, 다음 반복문부터 해당 원소가 0이면 다음 반복으로 넘어가도록 했다.
   1. 처음에 배수를 발견하면 카운트만 누적 해야겠다고 생각했는데, 그러면 2와 3의 공배수인 6일 경우에 중복카운팅 되는 경우가 있으므로 불가능하다.