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

 

 

에라토스테네스의 체를 구현하는 문제인데, 약간 다른 점이라면 K 번째로 삭제되는 숫자를 출력하는 것이므로 소수를 남기고 나머지를 모두 삭제하는 기존의 에라토스테네스의 체 알고리즘과 달리, 현재 판별 대상인 소수부터 삭제를 시작하여 그 배수인 숫자들을 연속으로 삭제하는 것이 특징이다!

 

 

def eratosthenes(N, K):
    num = [True]*(N+1)
    cnt = 0
    for i in range(2, N+1):
        if num[i]: # True 이면 소수이므로
            for j in range(i, N+1, i): # i의 배수 삭제
                if num[j]: # 이미 지운 숫자가 아니라면
                    num[j] = False
                    cnt += 1
                    if cnt == K:
                        return j

N, K = map(int, input().split())
result = eratosthenes(N,K)
print(result)

 

코드가 조금 더럽지만,, 일단 정답 코드는 위와 같다.

• eratosthenes 라는 이름의 함수를 만들어 입력값인 N과 K를 모두 인자로 받음
• num은 모든 값이 True로 이루어진 리스트로, 2부터 N까지의 모든 수를 소수 후보로 두며 초기에 모두 True로 설정
• 첫 번째 for 루프에서 2부터 N+1까지 순차적으로 순회하며 num[i]이 존재하는 경우, 즉 True(소수)인 경우 두 번째 for 루프에 진입하여 이후 작업을 진행시킨다.
• 두 번째 for 루프에서는 범위를 현재 숫자인 i 부터 N+1까지, 그리고 step은 i로 해서 범위 내의 i의 배수들만을 모두 순회하도록 범위를 설정함
• num[j]라면, 즉 두 번째 for 루프에서 순회하고 있는 숫자가 False가 아니어서 이미 지운 숫자가 아니라면 num[j]를 False로 저장한 뒤 cnt += 1 해준다.
• 이 작업을 반복하다가 추후 cnt값이 우리가 기다리고 있는 K와 같아지는 순간이 바로 K 번째로 삭제되는 숫자 j를 탐색하고 있는 순간이므로, j를 반환하고 종료한다!