Prime Number of Set Bits in Binary Representation | Set 2 | Function to create an array of prime numbers upto number 'n ; Create a boolean array " prime [ 0 . . n ] " and initialize all entries it as true . A value in prime [ i ] will finally be false if i is Not a prime , else true . ; If prime [ p ] is not changed , then it is a prime ; Update all multiples of p ; Append all the prime numbers to the list ; Utility function to count the number of set bits ; Driver program ; 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 .
' NEW_LINE import math as m NEW_LINE def SieveOfEratosthenes ( n ) : NEW_LINE INDENT prime = [ True for i in range ( n + 1 ) ] NEW_LINE p = 2 NEW_LINE while ( p * p <= n ) : NEW_LINE INDENT if ( prime [ p ] == True ) : NEW_LINE INDENT for i in range ( p * 2 , n + 1 , p ) : NEW_LINE INDENT prime [ i ] = False NEW_LINE DEDENT DEDENT p += 1 NEW_LINE DEDENT lis = [ ] NEW_LINE for p in range ( 2 , n + 1 ) : NEW_LINE INDENT if prime [ p ] : NEW_LINE INDENT lis . append ( p ) NEW_LINE DEDENT DEDENT return lis NEW_LINE DEDENT def setBits ( n ) : NEW_LINE INDENT return bin ( n ) [ 2 : ] . count ( '1' ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT x , y = [ 4 , 8 ] NEW_LINE count = 0 NEW_LINE primeArr = SieveOfEratosthenes ( int ( m . ceil ( m . log ( y , 2 ) ) ) ) NEW_LINE for i in range ( x , y + 1 ) : NEW_LINE INDENT temp = setBits ( i ) NEW_LINE if temp in primeArr : NEW_LINE INDENT count += 1 NEW_LINE DEDENT DEDENT print ( count ) NEW_LINE DEDENT