1.
Introduction
2.
Understanding the Problem
3.
Intuition
3.1.
Code
3.2.
Input
3.3.
Output
3.4.
Time Complexity
3.5.
Space Complexity
4.
Key Takeaways
Last Updated: Mar 27, 2024

# Kth Smallest Prime Number in range L to R for Q queries

Saksham Gupta
0 upvote

## Introduction

Maths is often considered as one of the toughest topics in school, but it's equally fun as well. It becomes even more fun when it's combined with programming . Yes, Today, we will discuss one such problem, i.e., Kth smallest Prime Number in range L to R for Q queries where your concepts related to programming and maths would be judged. Let’s understand the problem better.

## Understanding the Problem

We have been given three variables, namely ‘L,’ ‘R,’ and ‘Q,’ where [L, R] denotes the range and ‘Q’ denotes the total number of queries. Along with these queries, we will also be given a variable, ‘K’. Now our task is to find the Kth smallest prime number in the range [L, R]. If ‘K’ is greater than the count of prime numbers in the range [L, R], then return -1.

Let’s understand this better by the following example.

L = 4

R = 19

Q = 3

K = 1, 2, 3

Output

``````5
7
11``````

Explanation

We can see that prime numbers from 4 to 19 are 5, 7, 11, 13, 17, 19 in which 1st smallest is 5, 2nd is 7 and 3rd is 11.

Also see, Euclid GCD Algorithm

## 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!

Live masterclass