[백준/파이썬] 2960번 에라토스테네스의 체 풀이

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 2960번 에라토스테네스의 체
• 문제풀이 코드 GitHub 링크
• 제출 언어: Python 3

풀이

문제

에라토스테네스의 체를 수행할 때, K번째로 지워지는 수를 출력하는 문제입니다.

코드

n, k = map(int, input().split())

def eratos(n, k):
    n += 1
    sieve = [True] * n
    tmp = 0
    
    for i in range(2, n):
        if sieve[i] == True:
            for j in range(i, n, i):
                if sieve[j]:
                    tmp += 1
                    sieve[j] = False
                    if tmp == k:
                        print(j)
                        return

eratos(n, k)

설명

소수를 찾는 과정에서 배수를 지울 때마다 카운트를 올리고, 카운트가 K가 되는 순간의 값을 바로 출력하면 됩니다.

---

• 백준 문제풀이 전체 목록 보기

---