二进制表示中集合位的素数|集合 1
给定两个整数“L”和“R”,编写一个程序,找出在[L,R]范围内二进制表示中具有素数的集合位的总数。
示例:
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
说明:在这个程序中我们找到一个总数,就是有素数的集合位。所以我们使用一个 CPP 预定义函数_ _ builtin _ popcount()这些函数提供了一个总的设置位数。除了检查总比特是否是素数,如果是素数,我们增加计数器,这些过程重复直到给定的范围。
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
Python 3
# 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
服务器端编程语言(Professional Hypertext Preprocessor 的缩写)
<?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
?>
java 描述语言
<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>
Output:
4
时间复杂度:假设 n = (r-l) 那么整体时间复杂度为 N*sqrt(N) 我们可以使用厄拉多塞的筛来优化上面的解。 二进制表示中集合位的素数|集合 2
版权属于:月萌API www.moonapi.com,转载请注明出处