> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Prime Number of Set Bits in Binary

> Tested Python solution for LeetCode 762 with 20 pytest cases. Generate a practice environment with lcpy.

LeetCode 762, [Easy](/catalog/easy). Topics: [Math](/catalog/topics/math), [Bit Manipulation](/catalog/topics/bit-manipulation), Primality Test. [View on LeetCode](https://leetcode.com/problems/prime-number-of-set-bits-in-binary-representation/description/).

Generate this problem as a practice environment: tested reference solution, 20 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 762   # by problem number
lcpy gen -s prime_number_of_set_bits_in_binary_representation   # by problem name
```

## Problem

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.

### Examples

```
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.
```

```
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 \<= 10\<sup>6\</sup>
* 0 \<= right - left \<= 10\<sup>4\</sup>

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/prime_number_of_set_bits_in_binary_representation/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/prime_number_of_set_bits_in_binary_representation/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O((right - left) * log(right)) ~ O(w * 20) for w = right - left
    # Space: O(1)
    def count_prime_set_bits(self, left: int, right: int) -> int:
        primes = {2, 3, 5, 7, 11, 13, 17, 19}
        return sum(1 for n in range(left, right + 1) if n.bit_count() in primes)
```

## Complexity

| Time | Space |
| - | - |
| O((right - left) \* log(right)) \~ O(w \* 20) for w = right - left | O(1) |

## Tags


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.