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

구현 / 실버 4

♾️

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

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

 

 

내 풀이

N, K = map(int, input().split())
num = list(i for i in range(2, N+1))
ans = []

current_num = num[0]
prime = num[0] # prime의 배수를 지워야 함

while num:
    while current_num <= N:
        if current_num in num:
            ans.append(current_num)
            num.remove(current_num)
        current_num += prime

    if len(num) > 0:
        current_num = num[0]
        prime = num[0]

print(ans[K-1])

 

 

코드 설명

 

num: 2부터 N까지의 모든 정수를 저장하는 리스트

ans: 정답 리스트. 지워진 숫자가 순서대로 저장됨

current_num: 현재 숫자 (지울 대상)

prime: prime의 배수를 지울 예정

 

반복문에 들어가기 전, num의 가장 첫 번째 숫자(2)로 초기화한다.

current_num = num[0]
prime = num[0]

 

모든 숫자가 지워질 때까지 반복한다.

while num:

 

current_num(현재 숫자)가 N보다 작을 때까지 반복한다. (=prime의 모든 배수를 삭제)

리스트에 지울 숫자가 있다면 정답 리스트(ans)에 추가해 주고, num에서는 삭제한다.

현재 숫자를 prime만큼 증가시킨 배수 값으로 갱신한다.

while current_num <= N:
    if current_num in num:
        ans.append(current_num)
        num.remove(current_num)
    current_num += prime

 

모든 배수를 삭제한 뒤에도 남은 숫자가 있다면, 현재 숫자(current_num)와 소수(prime)값을 변경한다.

조건문을 넣지 않으면 IndexError: list index out of range 에러가 발생한다.

if len(num) > 0:
    current_num = num[0]
    prime = num[0]

 

 

코테 너무 오랜만에 풀어서 그런지 낯설다 ,, 🧐