Find the nth prime number

Given an integer n (1-indexed), return the n-th prime number (e.g., n=1 -> 2, n=2 -> 3, n=3 -> 5).

Design an algorithm that is efficient for moderately large n (you may state reasonable constraints, e.g., up to 10^5).

Find the Nth Prime Number

Given an integer n (1-indexed), return the n-th prime number. For example, the 1st prime is 2, the 2nd prime is 3, and the 3rd prime is 5. Design an algorithm that is efficient for moderately large n, so a simple trial-division approach for each candidate number is not sufficient.

Constraints

• 1 <= n <= 100000
• The answer fits in a 32-bit signed integer for the given constraints
• An efficient solution is expected, such as using the Sieve of Eratosthenes with a suitable upper bound

Examples

Example 1

Input: 1
Output: 2

Explanation: The 1st prime number is 2.

Example 2

Input: 2
Output: 3

Explanation: The sequence of primes starts as 2, 3, 5, 7, ...

Hints

1. Instead of testing each number individually for primality, mark multiples of known primes using a sieve.
2. To size the sieve, use an upper bound for the n-th prime: for n >= 6, p_n < n * (log n + log log n).