# Numbers with prime set bits in a given range using Sieve of Eratosthenes Algorithm

Objective: Given a range, find all the numbers in the range which has prime set bits using Sieve of Eratosthenes Algorithm.

Earlier we had seen a similar problem -Numbers with prime set bits in a given range solved in the naive approach. in this algorithm, we will improve the time complexity using the Sieve of Eratosthenes.

Example:

```L = 4, R = 10
Output: 5
Explanation:
4 = 1 0 0 ( not prime)
5 = 1 0 1 (prime)
6 = 1 1 0 (prime)
7 = 1 1 1 (prime)
8 = 1 0 0 0 ( not prime)
9 = 1 0 0 1 (prime)
10 = 1 1 0 0 (prime)
Total 5 numbers which has prime set bits.
```

Approach:

• Let’s say the given range is L and R.
• Find all the prime numbers from 1 to R (higher limit) using Sieve of Eratosthenes Algorithm and store it in the list.
• Now iterate through L to R and for each integer, count the number of set bits and check if that count is present in the list created in step 2. print it.

Complete Code:

Output:

```Numbers found for which set bits count is prime:
5 6 7 9 10
```

__________________________________________________
Top Companies Interview Questions..-

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________