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.