보통 에라토스테네스의 체 문제는 소수를 찾는 문제로 자주 등장한다. 에라토스테네스의 체의 원리는 다음과 같다.

• 1~100 범위의 수 안에서의 소수를 구한다고 가정한다.
• 가장 작은 수인 2는 소수 배열에 넣고 2의 배수를 모두 False로 체크해준다.
• 그 다음 작은 수인 3을 소수 배열에 넣고 3의 배수를 모두 False로 체크해준다.
• 그 다음 작은 수인 4는 이미 2의 배수로 False 체크가 되어 있으므로 그 다음 작은 수인 5를 소수 배열에 넣어주고 5의 배수를 모두 False 체크해준다.
• 100 이하의 범위에서 모두 처리해주면 소수 배열에는 1~100 범위의 소수만 들어가게 된다.

이 문제는 에라토스테네스의 체를 활용하여 해결하였다.

• n과 k를 입력받는다.
• k번째로 지운 수의 여부를 확인하기 위한 변수 cnt를 0으로 정의해준다.
• 2부터 n까지의 수를 채운 것을 구현하기 위한 num배열을 True로 채워준다.
• 2중 for문을 i와 j에 대해서 돌린다. 이때 i의 범위는 2부터 num배열의 길이+1이 되고, j의 범위는 i부터 n+1까지가 되고, j는 i씩 증가한다.
  -> 만약 num[j]가 True라면 이를 False로 변경해주고, cnt를 1 증가시킨다.
  -> 만약 cnt가 k와 같다면 j가 바로 k번째로 지운 수가 되므로 j를 출력해주고 break로 반복문을 탈출한다.

Code

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