09 Sept 2026•Easy•Go / Python / TypeScript

Prime Number of Set Bits in Binary Representation

Count integers in a range whose binary representation contains a prime number of set bits.

Use Kernighan's bit-clearing loop to count ones for each value and test the small result against the possible prime counts.

Complexity

O((right - left + 1) * log right) time and O(1) extra space.

Solution files

Go•prime-number-of-set-bits-in-binary-representation/solution.go

package main

import "math/bits"

func countPrimeSetBits(left int, right int) int {
	prime := map[int]bool{2: true, 3: true, 5: true, 7: true, 11: true, 13: true, 17: true, 19: true}
	answer := 0
	for value := left; value <= right; value++ {
		if prime[bits.OnesCount(uint(value))] {
			answer++
		}
	}
	return answer
}

Python•prime-number-of-set-bits-in-binary-representation/solution.py

class Solution:
    def countPrimeSetBits(self, left: int, right: int) -> int:
        primes = {2, 3, 5, 7, 11, 13, 17, 19}
        return sum(value.bit_count() in primes for value in range(left, right + 1))

TypeScript•prime-number-of-set-bits-in-binary-representation/solution.ts

function countPrimeSetBits(left: number, right: number): number {
  const primes = new Set([2, 3, 5, 7, 11, 13, 17, 19]);
  let answer = 0;
  for (let value = left; value <= right; value += 1) { let bits = 0; for (let n = value; n > 0; n &= n - 1) bits += 1; if (primes.has(bits)) answer += 1; }
  return answer;
}