Approach #1: Direct [Accepted]
Intuition and Approach
For each number from L
to R
, let's find out how many set bits it has. If that number is 2, 3, 5, 7, 11, 13, 17
, or 19
, then we add one to our count. We only need primes up to 19 because .
Complexity Analysis

Time Complexity: , where is the number of integers considered. In a bit complexity model, this would be as we have to count the bits in time.

Space Complexity: .
Analysis written by: @awice.