1363. The nth Prime
Print the nth prime number, counting 2 as the first.
1 -> 2 2 -> 3 3 -> 5 6 -> 13 100 -> 541
Testing each integer for primality in turn is O(n sqrt(n) log) overall and too
slow at n = 100000, where the answer is 1299709.
Sieve instead. The difficulty is that a sieve needs an upper bound, and the question gives a COUNT rather than a limit. Two ways out.
The estimate: the nth prime is below n * (ln n + ln ln n) for n at least 6,
which is a known bound and is tight enough to size the array directly.
The simpler route, and the one to reach for under pressure: sieve up to a limit
comfortably above the answer, here 2000000, and count off primes until the nth
appears. At these bounds that costs a few megabytes and a few milliseconds, and
it cannot be wrong for the stated range.
Take the second and say why. An interviewer is testing whether you noticed the missing bound at all, not whether you remember the estimate.
Count from 2, and be careful that 1 is not prime: an off-by-one here shifts every answer in the sequence.
Constraints - `1 ≤ n ≤ 100000`
Input
One line containing the integer n.
Output
Print one integer on its own line: the nth prime number, counting 2 as the first prime so that n = 1 prints 2.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.