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.
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.
Please read the Sieve of Eratosthenes Algorithm before continue reading.
- 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.
Numbers found for which set bits count is prime: 5 6 7 9 10