Dados dos enteros ‘L’ y ‘R’ , necesitamos escribir un programa que encuentre el conteo de números que tienen el número primo de bits establecidos en su representación binaria en el rango [L, R].
Ejemplos:
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
Para cada número en el rango [L, R], calculamos el número de bits establecidos. Usando la criba de Eratóstenes generamos una array de números primos hasta el último número del rango (es decir, R). Si el número de bits establecidos es primo, aumentamos la cuenta de los números y la imprimimos.
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>
Producción:
3
Este artículo es una contribución de Saisankar Gochhayat y Harshit Sidhwa . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a contribuido@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA