Find Nth Prime

Moderate
0/80
Average time to solve is 15m
20 upvotes
Asked in companies
OlaLivekeeping (An IndiaMART Company)UST Global

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).
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
3
5 
2
1
Sample Output 1:
11
3
2
Explanation for sample input 1:
For the first query, the prime numbers are [2, 3, 5, 7, 11]

For the second query, the prime numbers are [2, 3]

For the third query, the prime number is [2]
Sample Input 2:
3
46
20
13
Sample Output 2:
199
71
41
Hint

Try to check for each element, if it is prime or not and find Nth number that is prime.

Approaches (4)
Brute Force

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

  1. Initialize NUM to 1 and COUNT to 0.
  2. 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.
  3. Print NUM.
Time Complexity

O(Q * N^2), where N represents the Nth prime number that we have to find.

 

Since we are dividing every ith number from numbers from 2 to i, therefore, the time complexity of the approach is O(Q * N^2).

Space Complexity

O(1),

 

The space complexity of the approach is O(1) because no extra memory is required.

Code Solution
(100% EXP penalty)
Find Nth Prime
Full screen
Console