Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

The property concerns the number of ones in an integer's binary representation, not whether the integer itself is prime. Once primality answers are precomputed, each candidate only needs a set-bit count and one table lookup.

Approach

At module initialization, build a sieve of primality below one million. Mark zero and one nonprime, then mark multiples of each prime starting at its square. The table is much larger than the possible set-bit counts, but this is the preprocessing used by the reference solutions.
Iterate over every integer from left through right, including both endpoints.
Count its set bits and increment the answer if that count is marked prime.
Return the total. Powers of two have one set bit and are correctly excluded because one is not prime.

MX = 10**6
sieve = [True] * MX
sieve[0], sieve[1] = False, False

for i in range(int(sqrt(MX))):
    if sieve[i]:
        for j in range(i**2, MX, i):
            sieve[j] = False

class Solution:
    def countPrimeSetBits(self, left: int, right: int) -> int:
        res = 0

        for v in range(left, right + 1):
            if sieve[v.bit_count()]: res += 1
        
        return res

Complexity analysis

With M = 10^6, the displayed module performs a one-time sieve in O(M log log M) time and O(M) space. A call scans R = right - left + 1 integers. On a bit-cost model, counting the bits of each value costs O(log right) in both languages, so call time is O(R log right); under the stated fixed-width bound this is O(R) word-RAM time. Call-local auxiliary space is O(1) beyond the shared sieve.