A satellite ground station assigns every transponder a unique positive integer code. A code is considered "flagged" if the number of 1-bits in its binary representation (its Hamming weight, i.e. how many bits are set) is a prime number. For example, the code 11 is written 1011 in binary, which has three set bits, and 3 is prime, so 11 is flagged; the code 8 is written 1000, which has one set bit, and 1 is not prime, so 8 is not flagged.
Given two integers L and R, count how many transponder codes in the inclusive range [L, R] are flagged.
A single line containing two space-separated integers L and R.
A single integer: the number of integers x with L <= x <= R whose binary representation has a prime number of set bits.
1 <= L <= R <= 1000000
Example 1
Input
6 10
Expected
4
Explanation
The codes from 6 to 10 in binary are: 6=110 (2 set bits, prime), 7=111 (3 set bits, prime), 8=1000 (1 set bit, not prime), 9=1001 (2 set bits, prime), 10=1010 (2 set bits, prime). Four of the five codes (6, 7, 9, 10) are flagged, so the answer is 4.
Example 2
Input
10 15
Expected
5
Explanation
The codes from 10 to 15 in binary are: 10=1010 (2, prime), 11=1011 (3, prime), 12=1100 (2, prime), 13=1101 (3, prime), 14=1110 (3, prime), 15=1111 (4, not prime). Five of the six codes (10 through 14) are flagged, so the answer is 5.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →