풀이
에라토스테네스의 체를 구현하면서 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])