BOJ 2960번 : 에라토스테네스의 체 (Python/Silver 4)

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

---

설명

단순히 소수를 구하는 것이 아니다. 에라토스테네스의 체의 원리를 반영하면서 문제를 풀어줘야 한다. 다시 말해 2부터 N까지의 모든 정수 중 제일 작은 수부터 시작하여 그 소수의 배수들을 모두 지워나간다. 지워나갔으면, 안 지워진 가장 작은 수부터 또다시 반복한다. 여기까지가 에라토스테네스 체의 원리이다.

이 문제에서는 소수도 지워야 하고 배수도 지워야 하는데 그 과정에서 K번째로 지워지는 수를 찾는 것이다. 

 

풀이

➪ 에라토스테네의 체 알고리즘이 궁금하다면?

에라토스테네스의 체

 

Solution

#18:31 - 19:19
#문제 설명 : 2부터 N까지의 모든 정수 중 소수를 판별해 가면서 K번째로 지우는 수를 구한다.(소수도 지움)
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
m = int(N**0.5) #제곱근
a = [True]*(N+1) #소수 판정하기 위함

cnt = 0
for i in range(2, N+1): #제곱근으로 하니깐 안 됨 이유는? 소수를 찾는 것이 아니라 지워지는 숫자를 찾아야 하기 때문.
    if a[i] == True: #소수이면
        #a[i] = False #소수도 지우고 #이건 없어도 됨
        cnt += 1
        if cnt == K:
            print(i)
        for j in range(i + i, N + 1, i): #배수도 지우기
            if a[j] == True: #지워지지 않은 것만 
                a[j] = False
                cnt += 1
                if cnt == K:
                    print(j)

간단한 풀이

N, K = map(int, input().split())
cnt = 0
nums = [True] * (N + 1)
for i in range(2, len(nums) + 1):
    for j in range(i, N+1, i):
        if nums[j] == True:
            nums[j] = False
            cnt += 1
            if cnt == K:
                print(j)
                break