Prime Number of Set Bits in Binary Representation | Set 2 | Java code to find count of numbers having prime number of set bits in their binary representation in the range [ L , R ] ; function to create an array of prime numbers upto number ' n ' ; Create a boolean array " prime [ 0 . . n ] " and initialize all entries it as false . A value in prime [ i ] will finally be true if i is Not a prime , else false . ; 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 code ; 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 .
import java . util . * ; import java . lang . Math ; class GFG { static ArrayList < Integer > SieveOfEratosthenes ( int n ) { boolean [ ] prime = new boolean [ n + 1 ] ; for ( int p = 2 ; p * p <= n ; p ++ ) { if ( prime [ p ] == false ) for ( int i = p * 2 ; i < n + 1 ; i += p ) prime [ i ] = true ; } ArrayList < Integer > lis = new ArrayList < Integer > ( ) ; for ( int p = 2 ; p <= n ; p ++ ) if ( prime [ p ] == false ) lis . add ( p ) ; return lis ; } static int setBits ( int n ) { return Integer . bitCount ( n ) ; } public static int log2 ( int x ) { return ( int ) ( Math . log ( x ) / Math . log ( 2 ) + 1e-10 ) ; } public static void main ( String [ ] args ) { int x = 4 , y = 8 ; int count = 0 ; ArrayList < Integer > primeArr = new ArrayList < Integer > ( ) ; primeArr = SieveOfEratosthenes ( ( int ) Math . ceil ( log2 ( y ) ) ) ; for ( int i = x ; i < y + 1 ; i ++ ) { int temp = setBits ( i ) ; if ( primeArr . contains ( temp ) ) count += 1 ; } System . out . println ( count ) ; } }