Informatica Online Judge

  k번째 소수 구하기 [0860 / 035C]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 294   Total Tried : 388


The Champion of this Problem (C++) : whiteedu - ms / 261byte
My Best Submission (C++) : N/A

[]

Background

한 정수 k를 입력받아 k번째 소수를 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 k가 입력된다.

[입력값의 정의역]
1 <= k <= 100,000

Output

첫 번째 줄에 k번째 소수를 출력한다.

IO Example

입력
1

출력
2

입력
77

출력
389

* 입력값 k가 클 경우에 1초만에 구할 수 있는 방법에 대해서 수학적으로 고민해야 완벽하게 풀 수 있음.
즉 알고리즘의 계산량을 최소화 할 수 있는 방법은?

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]