Find the nth prime number
Company: NVIDIA
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
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).
Quick Answer: This question assesses algorithmic problem-solving and number-theoretic computation skills, requiring efficient prime generation and complexity analysis in the Coding & Algorithms domain.
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
Input: 1
Expected Output: 2
Explanation: The 1st prime number is 2.
Input: 2
Expected Output: 3
Explanation: The sequence of primes starts as 2, 3, 5, 7, ...
Hints
- Instead of testing each number individually for primality, mark multiples of known primes using a sieve.
- To size the sieve, use an upper bound for the n-th prime: for n >= 6, p_n < n * (log n + log log n).