Dados dos enteros ‘L’ y ‘R’, escriba un programa para encontrar los números totales que tienen un número primo de bits establecidos en su representación binaria en el rango [L, R].
Ejemplos:
Input : l = 6, r = 10 Output : 4 Explanation : 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) Hence count is 4 Input : l = 10, r = 15 Output : 5 10 -> 1010 (2 set bits, 2 is prime) 11 -> 1011 (3 set bits, 3 is prime) 12 -> 1100 (2 set bits, 2 is prime) 13 -> 1101 (3 set bits, 3 is prime) 14 -> 1110 (3 set bits, 3 is prime) Hence count is 5
Explicación: En este programa encontramos un número total, que tiene un número primo de bits establecidos. así que usamos una función predefinida de CPP __builtin_popcount() estas funciones proporcionan un conjunto total de bits en número. Además de verificar que el total de bits sea primo o no, si es primo, aumentamos el contador, este proceso se repite hasta el rango dado.
C++
// C++ program to count total prime
// number of set bits in given range
#include <bits/stdc++.h>
using namespace std;
bool isPrime(int n)
{
// Corner cases
if (n <= 1) return false;
if (n <= 3) return true;
// This is checked so that we can skip
// middle five numbers in below loop
if (n%2 == 0 || n%3 == 0) return false;
for (int i=5; i*i<=n; i=i+6)
if (n%i == 0 || n%(i+2) == 0)
return false;
return true;
}
// count number, that contains prime number of set bit
int primeBitsInRange(int l, int r)
{
// tot_bit store number of bit in number
int tot_bit, count = 0;
// iterate loop from l to r
for (int i = l; i <= r; i++) {
// use predefined function for finding
// set bit it is return number of set bit
tot_bit = __builtin_popcount(i);
// check tot_bit prime or, not
if (isPrime(tot_bit))
count++;
}
return count;
}
// Driven Program
int main()
{
int l = 6, r = 10;
cout << primeBitsInRange(l, r);
return 0;
}
Java
// Java program to count total prime
// number of set bits in given range
import java.lang.*;
class GFG{
static boolean isPrime(int n)
{
// Corner cases
if (n <= 1) return false;
if (n <= 3) return true;
// This is checked so that we can skip
// middle five numbers in below loop
if (n%2 == 0 || n%3 == 0) return false;
for (int i=5; i*i<=n; i=i+6)
if (n%i == 0 || n%(i+2) == 0)
return false;
return true;
}
// count number, that contains prime number of set bit
static int primeBitsInRange(int l, int r)
{
// tot_bit store number of bit in number
int tot_bit, count = 0;
// iterate loop from l to r
for (int i = l; i <= r; i++) {
// use predefined function for finding
// set bit it is return number of set bit
tot_bit = Integer.bitCount(i);
// check tot_bit prime or, not
if (isPrime(tot_bit))
count++;
}
return count;
}
// Driven Program
public static void main(String[] args)
{
int l = 6, r = 10;
System.out.println(primeBitsInRange(l, r));
}
}
// This code is Contributed by mits
Python3
# Python3 program to count total prime
# number of set bits in given range
def isPrime(n):
# Corner cases
if (n <= 1): return False;
if (n <= 3): return True;
# This is checked so that we can skip
# middle five numbers in below loop
if (n % 2 == 0 or n % 3 == 0):
return False;
i = 5;
while (i * i <= n):
if(n % i == 0 or n % (i + 2) == 0):
return False;
i = i + 6;
return True;
# count number, that contains
# prime number of set bit
def primeBitsInRange(l, r):
# tot_bit store number of
# bit in number
count = 0;
# iterate loop from l to r
for i in range(l, r + 1):
# use predefined function for finding
# set bit it is return number of set bit
tot_bit = bin(i).count('1');
# check tot_bit prime or, not
if (isPrime(tot_bit)):
count += 1;
return count;
# Driver Code
l = 6;
r = 10;
print(primeBitsInRange(l, r));
# This code is contributed by mits
C#
// C# program to count total prime
// number of set bits in given range
class GFG{
// To count the bits
static int BitCount(int n)
{
int count = 0;
while (n != 0)
{
count++;
n &= (n - 1);
}
return count;
}
static bool isPrime(int n)
{
// Corner cases
if (n <= 1) return false;
if (n <= 3) return true;
// This is checked so that we can skip
// middle five numbers in below loop
if (n%2 == 0 || n%3 == 0) return false;
for (int i=5; i*i<=n; i=i+6)
if (n%i == 0 || n%(i+2) == 0)
return false;
return true;
}
// count number, that contains prime number of set bit
static int primeBitsInRange(int l, int r)
{
// tot_bit store number of bit in number
int tot_bit, count = 0;
// iterate loop from l to r
for (int i = l; i <= r; i++) {
// use predefined function for finding
// set bit it is return number of set bit
tot_bit = BitCount(i);
// check tot_bit prime or, not
if (isPrime(tot_bit))
count++;
}
return count;
}
// Driven Program
public static void Main()
{
int l = 6, r = 10;
System.Console.WriteLine(primeBitsInRange(l, r));
}
}
// This code is Contributed by mits
PHP
<?php
// PHP program to count total prime
// number of set bits in given range
function BitCount($n)
{
$count = 0;
while ($n != 0)
{
$count++;
$n &= ($n - 1);
}
return $count;
}
function isPrime($n)
{
// Corner cases
if ($n <= 1) return false;
if ($n <= 3) return true;
// This is checked so that we can skip
// middle five numbers in below loop
if ($n % 2 == 0 || $n % 3 == 0)
return false;
for ($i = 5; $i * $i <= $n; $i = $i + 6)
if ($n % $i == 0 ||
$n % ($i + 2) == 0)
return false;
return true;
}
// count number, that contains
// prime number of set bit
function primeBitsInRange($l, $r)
{
// tot_bit store number of
// bit in number
$count = 0;
// iterate loop from l to r
for ($i = $l; $i <= $r; $i++)
{
// use predefined function for finding
// set bit it is return number of set bit
$tot_bit = BitCount($i);
// check tot_bit prime or, not
if (isPrime($tot_bit))
$count++;
}
return $count;
}
// Driver Code
$l = 6;
$r = 10;
echo primeBitsInRange($l, $r);
// This code is contributed by mits
?>
Javascript
<script>
// Javascript program to count total prime
// number of set bits in given range
// To count the bits
function BitCount(n)
{
count = 0;
while (n != 0)
{
count++;
n &= (n - 1);
}
return count;
}
function isPrime(n)
{
// Corner cases
if (n <= 1)
return false;
if (n <= 3)
return true;
// This is checked so that we can skip
// middle five numbers in below loop
if (n % 2 == 0 || n % 3 == 0)
return false;
for(i = 5; i * i <= n; i = i + 6)
if (n % i == 0 || n % (i + 2) == 0)
return false;
return true;
}
// Count number, that contains
// prime number of set bit
function primeBitsInRange(l, r)
{
// tot_bit store number of bit in number
var tot_bit, count = 0;
// Iterate loop from l to r
for(i = l; i <= r; i++)
{
// Use predefined function for finding
// set bit it is return number of set bit
tot_bit = BitCount(i);
// Check tot_bit prime or, not
if (isPrime(tot_bit))
count++;
}
return count;
}
// Driver code
var l = 6, r = 10;
document.write(primeBitsInRange(l, r));
// This code is contributed by Rajput-Ji
</script>
Producción:
4
Complejidad de tiempo: Vamos a n = (rl)
por lo que la complejidad de tiempo general es N * sqrt (N)
Podemos optimizar la solución anterior usando Sieve of Eratosthenes .
Número primo de bits establecidos en representación binaria | conjunto 2
Publicación traducida automáticamente
Artículo escrito por jaingyayak y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA