Prime Number of Set Bits in Binary Representation
We can define a helper function is_prime
to check if a number is prime.
To solve this problem, we need to iterate over the range from left
to right
(inclusive). For each number, we convert it to binary and count the set bits. Then we use the is_prime
function to check if the number of set bits is a prime number. We increment the counter if it is.
Here is the Python code:


The function bin(x)
converts an integer number to a binary string. The count('1')
function then counts the number of ‘1’ characters in the string, which corresponds to the number of set bits in the binary representation of the number.
Q&A
why my code is not running for long value such as 3 digit number range…..


Your original C++ code is generally correct in logic, but it can be optimized in terms of efficiency.
The isPrime
function, as it’s currently written, iterates over every number from 2 to n
to check whether n
is divisible by any of these numbers. This is not efficient for larger n
because it requires a lot of division operations. A more efficient approach is to check divisibility only up to the square root of n
, because a larger factor of n
would have a corresponding smaller factor that has already been tested.
Your count
function also has room for optimization. This function is using the Brian Kernighanâ€™s Algorithm to count the set bits in an integer. It’s generally an efficient way to count set bits, but when you know your input range, you can limit the calculations that you need to perform.
In your specific problem, you’re working with 32bit integers. Therefore, the maximum number of set bits in a number would be 32. But, since you only have to find the count of prime set bits, and the largest prime number less than 32 is 31, you only have to check for primes numbers up to 31. This can significantly reduce the number of iterations in your isPrime
function.
Here’s an optimized version of your C++ code:


This version of the code reduces the range of numbers checked in the isPrime
function to only up to the square root of n
, and keeps the countSetBits
function the same. The main function countPrimeSetBits
remains the same. This optimized version should run faster, especially for larger input ranges.


Problem Classification
Problem Category: This problem falls under the category of ‘Computational Number Theory’ and ‘Bit Manipulation’.
‘What’ Components:
 Range of numbers: The problem statement provides a range of integers, denoted by ’left’ and ‘right’.
 Binary representation: The solution requires dealing with the binary representation of numbers.
 Set bits: It’s necessary to count the number of set bits (1’s) in the binary representation.
 Prime numbers: The count of set bits is to be evaluated for primality.
 Counting the required numbers: The task is to count all the numbers in the range that meet the condition.
Problem Classification:
 Computational Number Theory: The problem involves prime numbers, which are a fundamental concept in number theory.
 Bit Manipulation: The binary representation of numbers and the operation of counting set bits both fall under bit manipulation.
Explanation: The problem requires the application of number theory (specifically, primality checking) to the count of set bits in binary representations of numbers. Therefore, it can be classified as a computational number theory problem. In addition, it involves binary representation and operations on bits, making it a bit manipulation problem. The goal is to count the numbers in a given range that have a prime number of set bits.
Language Agnostic Coding Drills
 Dissecting the Code:
Concepts found in this code include:
a. Use of sets for storing unique elements: primes = {2, 3, 5, 7, 11, 13, 17, 19}
b. Use of loops to iterate over a range of numbers: for i in range(left, right + 1)
c. Use of bit operations to count the number of set bits in a number: i.bit_count()
d. Checking for membership in a set: if i.bit_count() in primes
e. Updating and returning a counter: c += 1
and return c
 Listing and Classifying the Concepts:
a. Use of sets for storing unique elements  Beginner: Basic knowledge of Python data structures.
b. Use of loops to iterate over a range of numbers  Beginner: Fundamental programming concept.
c. Updating and returning a counter  Beginner: Basic concept of incrementing a counter variable.
d. Checking for membership in a set  Intermediate: Involves the knowledge of set operations.
e. Use of bit operations to count the number of set bits in a number  Intermediate: Requires understanding of binary representation and bitwise operations.
 ProblemSolving Approach:
Start by initializing a set of small prime numbers (up to 19, which is the number of bits in the binary representation of 10^6, the maximum possible ‘right’ value). Next, initialize a counter variable to zero.
Then, iterate over the inclusive range from ’left’ to ‘right’. For each number, count the number of set bits in its binary representation. If this count is in the prime set, increment the counter.
By iterating over all the numbers in the range, this approach ensures that all numbers with a prime number of set bits are counted. The use of the set makes the membership test efficient, as checking whether an element is in a set in Python takes constant time on average.
Finally, return the counter, which represents the total count of numbers in the range that have a prime number of set bits in their binary representation.
Each concept or drill plays a crucial role in the overall solution, contributing to either the iteration over the range, the calculation of the set bits, the prime check, or the count update.
Targeted Drills in Python
 PythonBased Coding Drills:
a. Use of sets for storing unique elements:


b. Use of loops to iterate over a range of numbers:


c. Updating and returning a counter:


d. Checking for membership in a set:


e. Use of bit operations to count the number of set bits in a number:


 ProblemSpecific Concepts:
The main problemspecific concept in this code is counting the number of set bits in an integer, and checking whether this count is prime. This concept is essential for our problem because the problem specifically asks us to count the numbers in a range that have a prime number of set bits in their binary representation.
 Integrating the Drills:
Start by initializing a set of small prime numbers (concept a). Also, initialize a counter to zero (concept c). Then, iterate over the inclusive range from ’left’ to ‘right’ (concept b). For each number, count the number of set bits in its binary representation (concept e). If this count is in the prime set, increment the counter (concept c and d). Finally, return the counter (concept c).
All of these concepts contribute to the final solution, and they can be assembled in this order to solve the initial problem.