This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

Given two integers `L`

and `R`

, find the count of numbers in the range `[L, R]`

(inclusive) having a prime number of set bits in their binary representation.

(Recall that the number of set bits an integer has is the number of `1`

s present when written in binary. For example, `21`

written in binary is `10101`

which has 3 set bits. Also, 1 is not a prime.)

**Example 1:**

Input:L = 6, R = 10Output:4Explanation:6 -> 110 (2 set bits, 2 is prime) 7 -> 111 (3 set bits, 3 is prime) 9 -> 1001 (2 set bits , 2 is prime) 10->1010 (2 set bits , 2 is prime)

**Example 2:**

Input:L = 10, R = 15Output:5Explanation:10 -> 1010 (2 set bits, 2 is prime) 11 -> 1011 (3 set bits, 3 is prime) 12 -> 1100 (2 set bits, 2 is prime) 13 -> 1101 (3 set bits, 3 is prime) 14 -> 1110 (3 set bits, 3 is prime) 15 -> 1111 (4 set bits, 4 is not prime)

**Note:**

`L, R`

will be integers`L <= R`

in the range`[1, 10^6]`

.`R - L`

will be at most 10000.

b'

\n#### Approach #1: Direct [Accepted]

\n

\n

'
\n\n

\n**Intuition and Approach**

For each number from `L`

to `R`

, let\'s find out how many set bits it has. If that number is `2, 3, 5, 7, 11, 13, 17`

, or `19`

, then we add one to our count. We only need primes up to 19 because .

**Complexity Analysis**

- \n
- \n
Time Complexity: , where is the number of integers considered. In a bit complexity model, this would be as we have to count the bits in time.

\n \n - \n
Space Complexity: .

\n \n

\n

Analysis written by: @awice.

\n