[백준] 2960번 에라토스테네스의 체

💡문제접근

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

💡테스트케이스3 설명

입력

10 7

출력

9

설명

2 → 4 → 6 → 8 → 10 → 3 → 6(X) → 9 → 5 → 7
6은 2의 배수를 제거하는 과정에서 먼저 제거되므로 뒤에서 6을 제거하는 과정을 거치면 안된다.

💡코드(메모리 : 30616KB, 시간 : 36ms)

N, K = map(int, input().split())
number_arr = [True] * (N+1)
number_arr[0] = False
number_arr[1] = False

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

이 문제에서 "지운다"는 게 "소수가 아니라고 판정했다"는 뜻이 아니다. 지운 건 그냥 지운 거고, 그 이전에 2번에서 찾은 P들은 소수가 맞다.

예를 들어, N=10이라고 하고 이 과정을 따라가보면,

처음에 2 3 4 5 6 7 8 9 10 의 수를 적는다.

지워지지 않은 수 중 가장 작은 수는 2이다. 따라서 2는 소수다. 이제 2를 비롯해서 2의 배수들을 모두 지운다.

3 5 7 9가 남았다. 다시 지워지지 않은 수 중 가장 작은 수는 3이다. 따라서 3도 소수다. 이제 3을 비롯해서 3의 배수들을 모두 지운다.

5 7이 남는다. 5가 제일 작으므로 5도 소수다. 5의 배수를 모두 지우면 7이 남고, 7도 소수가 된다.

💡소요시간 : 5m