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 .
< ? php function SieveOfEratosthenes ( $ n ) { $ prime = array_fill ( 0 , $ n + 1 , true ) ; for ( $ p = 2 ; $ p * $ p <= $ n ; $ p ++ ) { if ( $ prime [ $ p ] == true ) for ( $ i = $ p * 2 ; $ i < $ n + 1 ; $ i += $ p ) $ prime [ $ i ] = false ; } $ lis = array ( ) ; for ( $ p = 2 ; $ p <= $ n ; $ p ++ ) if ( $ prime [ $ p ] ) array_push ( $ lis , $ p ) ; return $ lis ; } function setBits ( $ n ) { $ cnt = 0 ; while ( $ n ) { if ( $ n & 1 ) $ cnt ++ ; $ n >>= 1 ; } ; return $ cnt ; } $ x = 4 ; $ y = 8 ; $ count = 0 ; $ primeArr = SieveOfEratosthenes ( ceil ( log ( $ y , 2 ) ) ) ; for ( $ i = $ x ; $ i < $ y + 1 ; $ i ++ ) { $ temp = setBits ( $ i ) ; if ( in_array ( $ temp , $ primeArr ) ) $ count += 1 ; } print ( $ count ) ; ? >