Here prime numbers are checked till the maximum number of bits possible because that the maximum bit sum possible is the number of bits itself .
vector < int > primeArr = SieveOfEratosthenes ( ceil ( log2 ( y ) ) ) ; for ( int i = x ; i < y + 1 ; i ++ ) { int temp = setBits ( i ) ; for ( int j = 0 ; j < primeArr . size ( ) ; j ++ ) { if ( temp == primeArr [ j ] ) { count += 1 ; break ; } } } cout << count << endl ; return 0 ; }