Prime Number of Set Bits in Binary Representation | Set 2 | C # 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 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 .
using System ; using System . Linq ; using System . Collections ; class GFG { static ArrayList SieveOfEratosthenes ( int n ) { bool [ ] prime = new bool [ 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 lis = new ArrayList ( ) ; for ( int p = 2 ; p <= n ; p ++ ) if ( prime [ p ] == false ) lis . Add ( p ) ; return lis ; } static int setBits ( int n ) { return ( int ) Convert . ToString ( n , 2 ) . Count ( c => c == '1' ) ; } public static void Main ( ) { int x = 4 , y = 8 ; int count = 0 ; ArrayList primeArr = new ArrayList ( ) ; primeArr = SieveOfEratosthenes ( Convert . ToInt32 ( Math . Ceiling ( Math . Log ( y , 2.0 ) ) ) ) ; for ( int i = x ; i < y + 1 ; i ++ ) { int temp = setBits ( i ) ; if ( primeArr . Contains ( temp ) ) count += 1 ; } Console . WriteLine ( count ) ; } }