Medium 0 solved 0% acceptance

Nth Prime

Return the nth prime number, counting 2 as the first.

What you'll learn

  • Generate primes in order
  • Choose a sieve size large enough for the answer
  • Compare trial division with a sieve

Problem

The primes in order are 2, 3, 5, 7, 11, 13, … Given a position n, return the prime at that position. Testing numbers one by one works for small n; for the larger inputs a sieve over a range that is big enough is much faster.

Implement nth_prime(n).

Input

n: The position in the list of primes, starting at 1.

Output

Return the nth prime. nth_prime(1) is 2.

Constraints

1 ≤ n ≤ 100,000

Examples

Example 1
Input:
n = 6

Expected output:
expected = 13
Input:
long long n = 6;

Expected output:
long long expected = 13;
Input:
long n = 6;

Expected output:
long expected = 13;

Explanation

The primes start 2, 3, 5, 7, 11, 13, so the sixth one is 13.

Example 2
Input:
n = 1

Expected output:
expected = 2
Input:
long long n = 1;

Expected output:
long long expected = 2;
Input:
long n = 1;

Expected output:
long expected = 2;

Explanation

The first prime is 2.

How to approach it

Try on your own first, then open one hint at a time.

Hint 1

Counting primes as you find them works, but testing every number by trial division gets slow for large n.

Hint 2

The 100,000th prime is below 1,300,000, so a sieve of that size is enough.

Hint 3

If your sieve turns out too small, double it and try again.

Expected complexity

O(m log log m) time, O(m) extra space, where m is the sieve size

References

This challenge is adapted for CodeUtility. Follow the statement and constraints above.

The best passing solution of each coder. Faster, smaller and better-reviewed solutions rank higher.

No passing solutions yet. Solve it to take first place.

Learn from others

Community solutions

No published solutions yet. Solve this challenge to share the first one.