[알고리즘/백준] 2960번 - 에라토스테네스의 체

🔗 문제 

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

level : 실버 4
문제 설명: 

에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다.
N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오.

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

---

🔮 풀이 아이디어

에라토스테네스의 체 알고리즘을 알고 있어서 먼저 함수로 작성 후에 코드를 문제에 맞게 수정하였다.

 

sieve라는 해당 인덱스의 소수 여부를 담고 있는 리스트를 선언해 준 후
에라토스테네스의 체 알고리즘을 통해 1~N까지의 수 중 소수만 남긴다.

여기서는 K번째 지워지는 수를 구하는 프로그램이기 때문에
반복문을 돌면서 소수에 해당하는 수, 그리고 지워지는 수를 차례대로 담은 리스트 order를 반환한다.

에라토스테네스의 체 알고리즘은 시간 복잡도를 줄이기 위해 반복문을 int(N ** 0.5)까지 돌리게 된다. 만약 N이 120이라면 11 * (2 ~ 10)까지는 이전 반복문에서 확인이 가능하기 때문에 11의 제곱인 121부터 검사를 해야 하는데 121은 120보다 작아 범위에 포함되지 않아서 검사할 필요가 없기 때문이다.

이러한 방식의 코드에서 수정했기 때문에 m + 1 이상인 소수가 order에 담기지 않아 따로 추가해 주었다.

 

order.extend([i for i in range(m + 1, N + 1) if sieve[i] is True])

원래 cnt라는 카운트 변수를 두어 시간을 줄이려고 했으나,
K, N의 범위가 1 ≤ K < N, max(1, K) < N ≤ 1000 로 주어져있고
현재 코드에서 if cnt == K: break 부분이 2번 들어가면서 코드가 길어지기 때문에 배열에 담는 방식을 선택했다.

 

최종 제출 코드

 

def order_of_erasing(N):
    sieve = [True] * (N + 1) # 체
    order = [] # 지워지는 순서

    m = int(N ** 0.5) # 마지막 체크 범위 구하기
    for i in range(2, m + 1):
        if sieve[i] is True:
            order.append(i)
            for j in range(i + i, N + 1, i):
                if sieve[j] is True:
                    sieve[j] = False
                    order.append(j)

    # 이후 추가되지 않은 소수들 포함하기
    order.extend([i for i in range(m + 1, N + 1) if sieve[i] is True])
    return order


N, K = map(int, input().split())
print(order_of_erasing(N)[K - 1])

---

📝 새로 공부한 내용

다른 사람의 풀이

n, k = map(int, input().split())
num = [1] * (n + 1)

for i in range(2, n + 1):
    if num[i] == 0: continue
    if k == 0: break

    for j in range(i, n + 1, i):
        if num[j]:
            num[j] = 0
            k -= 1
        if k == 0:
            print(j)
            break

 

다른 분의 풀이를 보면서 위에서도 계속 언급했듯이 원래 알고리즘에서 수정하다 보니 문제에서 요구하는 값만 구하는 데에 불필요한 코드가 포함되었다는 것을 느꼈다.

이 문제에서 소수 또한 지워지는 값이기 때문에 코드의 11번째 줄인 2번째 반복문에 포함되어서 작성이 가능하다는 것을 알 수 있다.
그리고 K번째를 직접 카운트하여 시간 또한 줄이는 방향으로 깔끔하게 코드를 짤 수 있지 않았을까 하는 아쉬움이 든다..!

---

📚 참고

에라토스테네스의 체 - 나무위키