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 bitsint setBits(int n){ return __builtin_popcount (n);}// Driver codeint 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 bitsstatic 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 codepublic 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 mdef 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 bitsdef setBits(n): return bin(n)[2:].count('1')# Driver programif __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 bitsstatic int setBits(int n){ return (int)Convert.ToString(n, 2).Count(c => c == '1');}// Driver programpublic 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 bitsfunction 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
This article is contributed by Saisankar Gochhayat and Harshit Sidhwa. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
