BOJ 2960 - 에라토스테네스의 체

풀이

---

에라토스테네스의 체를 구현하면서 K번째에 지워질 숫자를 찾는 문제이다.

소수를 판별하는 함수를 정의한 후 반복문을 통해 N까지의 정수 중 가장 작은 소수를 순서대로 찾는다.

소수를 찾은 경우 소수부터 N까지의 정수 중 소수의 배수를 찾아낸 후 정답배열에 삽입한다.

이때 찾아낸 정수가 이미 정답배열에 있는지 조건문을 통해 걸러낸다.

이후 완성된 정답배열에서 K번째 숫자를 호출하면된다.

소스코드

---

import sys
 
input = sys.stdin.readline
 
def isPrime(x):
    for i in range(2, x):
        if x%i == 0:
            return False
    return True
 
n, k = map(int, input().split())
primes = []
 
for i in range(2, n+1):
    if isPrime(i):
        primes.append(i)
        for j in range(i+1, n+1):
            if j%i == 0 and (j not in primes):
                primes.append(j)
 
print(primes[k-1])

References

---

• BOJ 2960 - 에라토스테네스의 체