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 .
function SieveOfEratosthenes ( n ) { let prime = new Array ( n + 1 ) . fill ( true ) ; for ( let p = 2 ; p * p <= n ; p ++ ) { if ( prime [ p ] == true ) for ( let i = p * 2 ; i < n + 1 ; i += p ) prime [ i ] = false ; } let lis = new Array ( ) ; for ( let p = 2 ; p <= n ; p ++ ) if ( prime [ p ] ) lis . push ( p ) ; return lis ; } function setBits ( n ) { let cnt = 0 ; while ( n ) { if ( n & 1 ) cnt ++ ; n >>= 1 ; } ; return cnt ; } let x = 4 ; let y = 8 ; let count = 0 ; let primeArr = SieveOfEratosthenes ( Math . ceil ( Math . log ( y , 2 ) ) ) ; for ( let i = x ; i < y + 1 ; i ++ ) { let temp = setBits ( i ) ; if ( primeArr . includes ( temp ) ) count += 1 ; } document . write ( count ) ;