Last Updated: 1 Dec, 2020

Find Nth Prime

Moderate

Asked in companies

Solve now

Problem statement

You are given a number 'N'. Your task is to find Nth prime number.

A prime number is a number greater than 1 that is not a product of two smaller natural numbers. Prime numbers have only two factors – 1 and the number itself.

Any number greater than 0 is a natural number i.e. natural numbers N = {1, 2, 3, 4,....}

For example:-

If you are asked to find the 7th prime number, it’ll be 17 because the first 7 prime numbers are 2, 3, 5, 7, 11, 13, 17.

Note: 1 is not a prime number.

Follow Up:

Try to solve the problem in O(N log log N) + O(N).

Input Format :

The first line of input contains an integer 'Q' representing the number of the queries. Then Q queries follow:

The first line of each query contains an integers ‘N’ representing the number of a prime number to be found.

Output Format :

For each query, return the Nth prime number. 

Print the output of each query in a separate line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1 <= Q <= 100
1 <= N <= 10^4

Time Limit: 1 sec

Solve now

Approaches

01 Approach

Consider a function FINDPRIME that takes number N as input parameter and do:

Initialize NUM to 1 and COUNT to 0.
Iterate for COUNT, while COUNT<=N:
1. Increment NUM by 1
2. Iterate for each 2<= i <= NUM and check:
  1. If NUM % i == 0, break the loop.
3. Check if i == NUM, it is a prime number. Do:
  1. Increment COUNT by 1.
Print NUM.

Solve now

02 Approach

Define MAXSIZE as 10^6+5 and an empty ARRAYOFPRIMES.
Initialize boolean array ISPRIME[i] to TRUE for each 2<=i <=MAXSIZE
Iterate for each 2 <= p <= MAXSIZE:
1. If IsPrime[P] is not changed, then it is a prime. I.e. if ISPRIME[P] is TRUE:
  1. Update all multiples of P greater than or equal to the square of it numbers which are multiples of p and are less than P^2 are already been marked, i.e. for each P*P <= i <= MAXSIZE:
    1. Assign FALSE to ISPRIME[i] and increment i by P.
Store all prime numbers in an array, i.e. for each 2<= P <= MAXSIZE, if ISPRIME[P] is TRUE then add P to ARRAYOFPRIMES.
Return ARRAYOFPRIMES[N].

Solve now

03 Approach

We can use some basic OOPs techniques to reduce complexity. We'll create a global sieve and store values of prime numbers in it and use it to get prime numbers for all queries in constant time.

Define global variable MAXSIZE as 10^6+5 and an empty ARRAYOFPRIMES.
Initialize boolean array ISPRIME[i] to TRUE for each 2<=i <=MAXSIZE
Iterate for each 2 <= p <= MAXSIZE:
1. If IsPrime[P] is not changed, then it is a prime. I.e. if ISPRIME[P] is TRUE:
  1. Update all multiples of P greater than or equal to the square of it numbers which are multiples of p and are less than P^2 are already been marked, i.e. for each P*P <= i <= MAXSIZE:
    1. Assign FALSE to ISPRIME[i] and increment i by P.
Store all prime numbers in an array, i.e. for each 2<= P <= MAXSIZE, if ISPRIME[P] is TRUE then add P to ARRAYOFPRIMES.

Now, once the array is created, you can check and return ARRAYOFPRIMES[N]. Thus the retrieval of Nth prime number can be done in constant time.

Solve now

04 Approach

Consider function FINDNTHPRIME that accepts an integer N as a parameter and do:

Define ArrayLists ISPRIME, PRIMENUMBER and SPF (Smallest Prime Factor).
Set ISPRIME false for 0 and 1
For each 2<= i <= N do:
1. If ISPRIME is TRUE for i then i is prime number. Do:
  1. Add i to PRIMENUMBER
  2. Set SPF of i as i
Remove all multiples of i*PRIME[j] which are not prime by making ISPRIME[i*PRIME[j]] = FLASE and put smallest prime factor of i*PRIME[j] as PRIME[j] [for exp :let i = 5, j = 0, PRIME[j] = 2 [ i*PRIME[j] = 10] so smallest prime factor of '10' is '2' that is PRIME[j] ]. This loop run only one time for number which are not prime.
Iterate for each j from 0 till PRIME.SIZE() and i*PRIME[j] < N and PRIME[j] <= SPF[i] and do:
1. Set ISPRIME[i*PRIME[j]] as FALSE.
2. Put smallest prime factor of i*PRIME[j]. Assign PRIME[j] to SPF[i*PRIME[j]].
Return PRIME[N].

Solve now