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!
38+ registered 