Prime Set Bits in Range
EasyBit ManipulationMath
Description
Count integers i in the inclusive range [l, r] whose binary representation has a prime number of set bits.
Examples
Input:
l = 6, r = 10Output:
4Explanation:
Bits counts 2,3,1,2,2 — four are prime (2 or 3).
Input:
l = 10, r = 15Output:
5Explanation:
Counts 2,2,3,2,3,4 — five are prime.
Input:
l = 1, r = 1Output:
0Explanation:
popcount(1)=1, not prime.
Constraints
- •
1 ≤ l ≤ r ≤ 10⁶