Find Nth Prime
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).

Input Format :

The first line of input contains an integer 'Q' representing the number of the queries. Then the 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

Question

Find Nth Prime

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).

Input Format :

The first line of input contains an integer 'Q' representing the number of the queries. Then the 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

Accepted Answer

The task is to find the Nth prime number given a number N.

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.
Start with a counter at 0 and a number at 2.
Increment the number by 1 and check if it is prime.
If it is prime, increment the counter.
Repeat until the counter reaches N.
Return the last prime number found.

Accepted Answer

Approach (Using Sieve of Eratosthenes) :

1) 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.

2) Define global variable MAXSIZE as 10^6+5 and an empty ARRAYOFPRIMES.

3) Initialize boolean array ISPRIME[i] to TRUE for each 2<=i <=MAXSIZE

4) Iterate for each 2 <= p <= MAXSIZE :
4.1) If IsPrime[P] is not changed, then it is a prime. I.e. if ISPRIME[P] is TRUE :
i) 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:

ii) Assign FALSE to ISPRIME[i] and increment i by P.

5) Store all prime numbers in an array, i.e. for each 2<= P <= MAXSIZE, if ISPRIME[P] is TRUE then add P to ARRAYOFPRIMES.

6) 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.

TC : O(N* log(log N)), where N = the Nth prime number that we have to find.
SC : O(N)

Accepted Answer

Brute Force

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.

Space Complexity: O(1)Explanation:

O(1),

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

Time Complexity: O(n)Explanation:

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).

Accepted Answer

Sieve of Eratosthenes

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].

Space Complexity: O(n)Explanation:

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

The space complexity of the approach is O(N) because we are creating an extra array in memory of size N.

Time Complexity: OtherExplanation:

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

For the Sieve of Eratosthenes, the basic idea is to progressively remove numbers that are not prime. First, we start with even numbers i.e. which are divisible by 2. Then we remove all numbers, divisible by 3, then by 5 (we skip 4, because it is already divisible by 2) and so on. Which gives us a Harmonic Progression that has the time complexity of O(Q * N * log(log (N)))

Accepted Answer

Global Sieve of Eratosthenes

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.

Space Complexity: O(1)Explanation:

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

The space complexity of the approach is O(N) because we are creating an extra array in memory of size N.

Time Complexity: O(1)Explanation:

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

Here we are using the same Sieve of Eratosthenes, but with optimisation of storing the prime numbers, up to N therefore this has the time complexity of O(N* log(log N)).

Accepted Answer

Modified global sieve

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].

Space Complexity: O(n)Explanation:

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

The space complexity of the approach is O(N) because we are creating an extra array in memory of size N.

Time Complexity: O(1)Explanation:

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

Since here we are running only a single loop once to filter out all the numbers in the range [2;N] therefore the time complexity of the approach is O(N).

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:-

Note: 1 is not a prime number.

Follow Up:

Input Format :

Output Format :

Note:

Constraints:

Top UST Senior Software Engineer interview questions & answers

Popular interview questions of Senior Software Engineer

Top HR questions asked in UST Senior Software Engineer