## Intuition

The intuition is to use the__ Sieve of Eratosthenes__, which is quite obvious as we have to deal with prime numbers __here__.

*But how?*

In the range of [L, R], we will run Sieve of Eratosthenes. Now we will know which all numbers in this range are prime or not. In each query, we will be given ‘K’; thus, we will find the Kth smallest prime from the above-calculated primes. Things will become more clear from the code.

### Code

```
#include <iostream>
#include <vector>
using namespace std;
vector<bool> primes;
// Function to implement Sieve Of Eratosthenes
void sieveOfEratosthenes(int r)
{
primes.assign(r + 1, true);
primes[1] = false;
int i = 2;
while (i * i <= r)
{
if (primes[i] == true)
{
int j = i + i;
while (j <= r)
{
primes[j] = false;
j += i;
}
}
i++;
}
}
// Function, which will return our answer.
int kthSmallest(int l, int r, int k)
{
// To count the prime number
int count = 0;
int i = l;
// Iterating from 'L' to 'R.’
while (i <= r)
{
// If it's a prime number.
if (primes[i] == true)
{
count++;
}
// If we reach the Kth prime number.
if (count == k)
{
return i;
}
i++;
}
// If we are not able to find Kth smallest prime number.
return -1;
}
// Driver Code
int main()
{
int q, l, r, k;
// Taking Input.
cin >> l >> r;
cin >> q;
// Calling Sieve Of Eratosthenes.
sieveOfEratosthenes(r);
// For each query.
for (int i = 0; i < q; i++)
{
cin >> k;
cout << kthSmallest(l, r, k) << endl;
}
return 0;
}
```

### Input

```
4 19
3
1 2 3
```

### Output

```
5
7
11
```

### Time Complexity

**O(R * log(log(R)) + Q * (L - R))**, where ‘Q’ is the number of queries and ‘L,’ and ‘R’ are lower and upper bounds, respectively.

As we are using Sieve of Eratosthenes which will cost us O(R * log(log(R))) time and also as there are ‘Q’ queries and in each query, we loop from ‘L’ to ‘R’ it will cost us O(Q * (L - R)) time. Thus,** **the overall time complexity is **O(R * log(log(R)) + Q * (L - R))**.

### Space Complexity

**O(R)**, where ‘R’ is the upper limit.

As we are using an array, ‘PRIMES’ of size ‘R.’

## Key Takeaways

We saw how we solved the problem ‘Find Prime numbers in a 2D Array (Matrix)’ by both Naive as well as efficient methods, namely Sieve of Eratosthenes. You must be thrilled about learning a new concept but the road to become a champ coder is still very long. So head over to our practice platform __Coding Ninjas Studio__ to practice top problems on every topic, interview experiences, and many more. Till then, Happy Coding!