09 Sept 2026•Go / Python / TypeScript•Easy

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
Python prime-number-of-set-bits-in-binary-representation/solution.py
TypeScript prime-number-of-set-bits-in-binary-representation/solution.ts

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 = {class="syntax-number">2, class="syntax-number">3, class="syntax-number">5, class="syntax-number">7, class="syntax-number">11, class="syntax-number">13, class="syntax-number">17, class="syntax-number">19}
        return sum(value.bit_count() in primes for value in range(left, right + class="syntax-number">1))

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

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