## Algorithm

Problem Name: 762. Prime Number of Set Bits in Binary Representation

Given two integers `left` and `right`, return the count of numbers in the inclusive range `[left, right]` 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.

Example 1:

```Input: left = 6, right = 10
Output: 4
Explanation:
6  -> 110 (2 set bits, 2 is prime)
7  -> 111 (3 set bits, 3 is prime)
8  -> 1000 (1 set bit, 1 is not prime)
9  -> 1001 (2 set bits, 2 is prime)
10 -> 1010 (2 set bits, 2 is prime)
4 numbers have a prime number of set bits.
```

Example 2:

```Input: left = 10, right = 15
Output: 5
Explanation:
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)
5 numbers have a prime number of set bits.
```

Constraints:

• `1 <= left <= right <= 106`
• `0 <= right - left <= 104`

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
int numOfBits(n) {
int k = 0;
while (n) {
k ++;
n = n & (n - 1);
}
return k;
}
​
int countPrimeSetBits(int L, int R){
int k = (1 << 2) |
(1 << 3) |
(1 << 5) |
(1 << 7) |
(1 << 11) |
(1 << 13) |
(1 << 17) |
(1 << 19);
int ans = 0;
while (L <= R) {
if ((k >> numOfBits(L)) & 1) ans ++;
/* equals to:
if (numOfBits(L) is 2 or 3 or 5 or 7 ...
*/

}
return ans;
}
``````
Copy The Code &

Input

cmd
left = 6, right = 10

Output

cmd
4

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
const countPrimeSetBits = function(L, R) {
let res = 0;
for (let i = L; i <= R; i++) {
if (chkPrime(i)) {
res += 1;
}
}
return res;
};

function chkPrime(num) {
const str = bin(num);
const snum = setNum(str);
return isPrime(snum);
}

function setNum(str) {
let num = 0;
for (let i = 0; i < str.length; i++) {
if (str.charAt(i) === "1") {
num += 1;
}
}
return num;
}

function bin(num) {
return (num >>> 0).toString(2);
}
function isPrime(num) {
for (let i = 2; i < num; i++) {
if (num % i === 0) return false;
}
return num !== 1;
}
``````
Copy The Code &

Input

cmd
left = 6, right = 10

Output

cmd
4

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def countPrimeSetBits(self, L, R):
"""
:type L: int
:type R: int
:rtype: int
"""
count=0
while L<=R:
if str(bin(L)[2:]).count("1") in [2,3,5,7,11,13,17,19]: count+=1
if str(bin(R)[2:]).count("1") in [2,3,5,7,11,13,17,19]:
count+=1
if L==R: count-=1
L+=1
R-=1
return count
``````
Copy The Code &

Input

cmd
left = 10, right = 15

Output

cmd
5

### #4 Code Example with C# Programming

```Code - C# Programming```

``````
namespace LeetCode
{
{
public int CountPrimeSetBits(int L, int R)
{
var count = 0;
for (int i = L; i <= R; i++)
{
var bits = CountBits(i);
if (bits == 2 || bits == 3 || bits == 5 || bits == 7 ||
bits == 11 || bits == 13 || bits == 17 || bits == 19)
count++;
}

return count;
}

private int CountBits(int num)
{
var count = 0;
while (num > 0)
{
num &= num - 1;
count++;
}

return count;
}
}
}
``````
Copy The Code &

Input

cmd
left = 10, right = 15

Output

cmd
5