에라토스테네스의 체

이는 소수를 판별하는 알고리즘이다.
알고리즘의 원리는 2부터 시작하여 특정 수의 배수에 해당되는 수들을 모두 배제하는 방식이다.
배제되지 않은 수들은 비로소 소수라고 판단할 수 있으며,
소수 발견시 똑같이 그 소수의 배수를 모두 배제한다(자기 자신 뺴고)

Process

• 이미 방문한 수가 아닌 경우, 즉 다른 수의 배수가 아니기에 소수로 판단되는 수일 경우,
  • 그 수의 배수들을 모두 방문 처리(소수 아님 처리)를 한다.
  • n 이하의 배수들을 모두 처리한 후, 다음 수로 넘어간다.
• 만약 방문한 수인 경우, 소수가 아니므로 다음 반복으로 넘어간다.
• 위 두 과정을 2부터 시작하여 반복한다.
• 이때, 방문 처리를 할 때마다 cnt를 하며, cnt == k일 경우 반복을 종료한다
  
  

코드

if __name__ == "__main__":
     n, k = map(int, input().split())
     visited = {i: False for i in range(2, n+1)}
     cnt = 0
     
     for p in range(2, n + 1):
          temp = p
          while temp <= n:
               if not visited[temp]:
                    cnt += 1
                    visited[temp] = True
                    if cnt == k:
                         print(temp)
                         exit(0)
               temp += p