Prime Number of Set Bits in Binary Representation
Problem
Count integers in [L, R] whose binary representation has a prime number of set bits. Since values are at most 1e6, set-bit counts are small.
L=6, R=104def countPrimeSetBits(L, R):
primes = {2,3,5,7,11,13,17,19,23,29,31}
return sum(1 for x in range(L, R+1) if bin(x).count('1') in primes)function countPrimeSetBits(L, R) {
const primes = new Set([2,3,5,7,11,13,17,19,23,29,31]);
let ans = 0;
for (let x = L; x <= R; x++) {
let c = 0, y = x;
while (y) { c += y & 1; y >>>= 1; }
if (primes.has(c)) ans++;
}
return ans;
}int countPrimeSetBits(int L, int R) {
Set<Integer> primes = Set.of(2,3,5,7,11,13,17,19,23,29,31);
int ans = 0;
for (int x = L; x <= R; x++)
if (primes.contains(Integer.bitCount(x))) ans++;
return ans;
}int countPrimeSetBits(int L, int R) {
set<int> primes = {2,3,5,7,11,13,17,19,23,29,31};
int ans = 0;
for (int x = L; x <= R; x++)
if (primes.count(__builtin_popcount(x))) ans++;
return ans;
}Explanation
We want to count how many numbers in the range [L, R] have a prime number of set bits. The clever shortcut is that the values are at most about a million, which fits in roughly 20 bits — so the count of 1 bits can never exceed about 20.
That means the only possible prime bit-counts are small ones. We precompute them once in a set: primes = {2,3,5,7,11,13,17,19,23,29,31}. Checking membership in this set is instant.
Then we simply walk every number x from L to R, count its set bits with bin(x).count('1'), and add 1 to the answer whenever that count is in primes.
Example: range [6, 10]. Their bit counts are 6=110 (2), 7=111 (3), 8=1000 (1), 9=1001 (2), 10=1010 (2). The counts 2, 3, 2, 2 are prime but 1 is not, so 4 values qualify.
It works because we only ever test bit-counts against a tiny fixed list of primes, making each check trivial.