Prime Number of Set Bits in Binary Representation | Set 2
Given two integers ‘L’ and ‘R’, we need to write a program that finds the count of numbers having the prime number of set bits in their binary representation in the range [L, R].
Examples:
Input : 6 10 Output : 4 6 -> 110 (2 set bits, 2 is prime) 7 -> 111 (3 set bits, 3 is prime) 9 -> 1001 (2 set bits , 2 is prime) 10->1010 (2 set bits , 2 is prime) Input : 10 15 Output : 5 10 -> 1010(2 number of set bits) 11 -> 1011(3 number of set bits) 12 -> 1100(2 number of set bits) 13 -> 1101(3 number of set bits) 14 -> 1110(3 number of set bits) 15 -> 1111(4 number of set bits) Hence total count is 5
For each number in the range [L, R], we calculate the number of set bits. Using Sieve of Eratosthenes we generate a prime array up to the last number in the range (i.e. R). If the number of set bits is prime, we increase the count of the numbers and print it.
C++
// C++ code to find count of numbers // having prime number of set bits // in their binary representation in // the range [L, R] #include<bits/stdc++.h> using namespace std; #include <cmath> // Function to create an array of prime // numbers upto number 'n' vector< int > SieveOfEratosthenes( int 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. bool prime[n + 1]; memset (prime, false , sizeof (prime)); for ( int p = 2; p * p <= n; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p] == false ) // Update all multiples of p for ( int i = p * 2; i < n + 1; i += p) prime[i] = true ; } vector< int > lis; // Append all the prime numbers to the list for ( int p = 2; p <=n; p++) if (prime[p] == false ) lis.push_back(p); return lis; } // Utility function to count // the number of set bits int setBits( int n){ return __builtin_popcount (n); } // Driver code int main () { int x = 4, y = 8; int count = 0; // 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. vector< int > primeArr = SieveOfEratosthenes( ceil (log2(y))); for ( int i = x; i < y + 1; i++) { int temp = setBits(i); for ( int j=0;j< primeArr.size();j++) { if (temp == primeArr[j]) {count += 1; break ; } } } cout << count << endl; return 0; } // This code is contributed by mits |
Java
// Java code to find count of numbers having // prime number of set bits in their binary // representation in the range[L, R] import java.util.*; import java.lang.Math; class GFG { // function to create an array of prime // numbers upto number 'n' static ArrayList<Integer> SieveOfEratosthenes( int 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. boolean [] prime = new boolean [n + 1 ]; for ( int p = 2 ; p * p <= n;p++) { // If prime[p] is not changed, then it is a prime if (prime[p] == false ) // Update all multiples of p for ( int i = p * 2 ; i < n + 1 ; i += p) prime[i] = true ; } ArrayList<Integer> lis = new ArrayList<Integer>(); // append all the prime numbers to the list for ( int p = 2 ; p <=n; p++) if (prime[p] == false ) lis.add(p); return lis; } // utility function to count the number of set bits 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 ); } // Driver code public static void main (String[] args) { int x = 4 , y = 8 ; int count = 0 ; ArrayList<Integer> primeArr = new ArrayList<Integer>(); // 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. 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); } } // This code is contributed by mits. |
Python
# Python 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' import math as m def SieveOfEratosthenes(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. prime = [ True for i in range (n + 1 )] p = 2 while (p * p < = n): # If prime[p] is not changed, then it is a prime if (prime[p] = = True ): # Update all multiples of p for i in range (p * 2 , n + 1 , p): prime[i] = False p + = 1 lis = [] # Append all the prime numbers to the list for p in range ( 2 , n + 1 ): if prime[p]: lis.append(p) return lis # Utility function to count the number of set bits def setBits(n): return bin (n)[ 2 :].count( '1' ) # Driver program if __name__ = = "__main__" : x, y = [ 4 , 8 ] count = 0 # 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. primeArr = SieveOfEratosthenes( int (m.ceil(m.log(y, 2 )))) for i in range (x, y + 1 ): temp = setBits(i) if temp in primeArr: count + = 1 print (count) |
C#
// C# code to find count of numbers having prime number // of set bits in their binary representation in the range // [L, R] using System; using System.Linq; using System.Collections; class GFG{ // Function to create an array of prime // numbers upto number 'n' static ArrayList SieveOfEratosthenes( int 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. bool [] prime = new bool [n+1]; for ( int p=2;p * p <= n;p++) { // If prime[p] is not changed, then it is a prime if (prime[p] == false ) // Update all multiples of p for ( int i=p * 2;i<n+1;i+=p) prime[i] = true ; } ArrayList lis = new ArrayList(); // append all the prime numbers to the list for ( int p=2;p<=n;p++) if (prime[p]== false ) lis.Add(p); return lis; } // Utility function to count the number of set bits static int setBits( int n){ return ( int )Convert.ToString(n, 2).Count(c => c == '1' ); } // Driver program public static void Main () { int x=4, y=8; int count = 0; ArrayList primeArr= new ArrayList(); // 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. 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); } } // This code is contributed by mits |
PHP
<?php // PHP 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' function SieveOfEratosthenes( $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. $prime = array_fill (0, $n +1,true); for ( $p = 2; $p * $p <= $n ; $p ++) { // If prime[p] is not changed, then it is a prime if ( $prime [ $p ] == true) // Update all multiples of p for ( $i = $p * 2; $i < $n +1; $i += $p ) $prime [ $i ] = false; } $lis = array (); // Append all the prime numbers to the list for ( $p =2; $p <= $n ; $p ++) if ( $prime [ $p ]) array_push ( $lis , $p ); return $lis ; } // Utility function to count the number of set bits function setBits( $n ) { $cnt =0; while ( $n ){ if ( $n &1) $cnt ++; $n >>=1;}; return $cnt ; } // Driver program $x = 4; $y = 8; $count = 0; // 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. $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 ); // This code is contributed by mits ?> |
Javascript
<script> // Javascript 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' function SieveOfEratosthenes(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. let prime = new Array(n+1).fill( true ); for (let p = 2;p * p <= n;p++) { // If prime[p] is not changed, then it is a prime if (prime[p] == true ) // Update all multiples of p for (let i=p * 2;i<n+1;i+=p) prime[i] = false ; } let lis = new Array(); // Append all the prime numbers to the list for (let p=2;p<=n;p++) if (prime[p]) lis.push(p); return lis; } // Utility function to count the number of set bits function setBits(n) { let cnt=0; while (n){ if (n&1)cnt++;n>>=1;}; return cnt; } // Driver program let x = 4; let y = 8; let count = 0; // 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. 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); // This code is contributed by gfgking </script> |
Output:
3