如果数字是正整数并且其二进制展开中的设置位数是素数，则该数字被认为是有害的。第一个有害数字是 3，因为 3 = (11)
2
。可以看出3的二进制表示的设定位数为2，是一个素数。
前10个有害数字是3、5、6、7、9、10、11、12、13、14。有趣的是，2的幂永远不可能是有害数字，因为它们总是只有1个设置位。1不是质数。另一方面，所有可以表示为2
n
+ 1的数字，其中n是任意自然数，将始终是有害数字，因为它们将有2个设置位，而我们知道2是一个质数。
牢记这些有害数字的特性，下面的文章讨论了一种检查一个数字是否为有害数字的方法。
问题陈述
此问题旨在检查给定数字 n 是否是一个有害数字，即它是一个正数，在其二进制展开中具有质数个设置位。
示例
Explanation
的翻译为：
解释
37 = 100101 的二进制表示。
设置位数 = 3
由于 3 是素数，因此 37 是一个有害的数字。
Explanation
的翻译为：
解释
22 = 10110 的二进制表示。
设置位数 = 3。
由于3是一个质数，22是一个恶毒数。
Explanation
的翻译为：
解释
71的二进制表示为1000111。
设置位数 = 4。
由于 4 不是质数，因此 71 也不是有害数字。
Explanation
的翻译为：
解释
64的二进制表示为1000000。
设置位数 = 1。
由于64 = 2
6
，即它是2的幂，它有1个设置位。由于1不是质数，64不是一个恶性数。
解决方案
我们必须知道设置位数是否为质数，以便确定一个数是否是恶性的。手头的主要任务是计算该数的二进制展开中的设置位数。以下方法可用于计算设置位数，然后确定结果是否为质数。
该方法包括以下步骤 -
使用循环和右移运算符迭代数字的所有位。
如果位值为 1，则设置位的计数加 1。
检查计数的最终值是否为质数。
显示答案。
算法
函数 is_prime()
如果 (n
返回错误
for (i从2到√a)
如果（a%i==0）
返回错误
返回 true
函数count_set_bits()
初始化计数器 = 0
当 (n > 0)
如果 ((n & 1) > 0)
计数器 = 计数器 + 1
n = n >> 1
退货柜台
函数 is_pernious()
初始化计数器
计数器 = count_set_bits(n)
if (is_prime(counter) == true)
返回真
其他
返回错误
函数main()
初始化n
if (is_pernious())
cout
其他
cout << “非有害数字”
打印输出
示例：C++ 程序
程序使用函数
is_pernicious()
确定数字是否有害。它通过在函数
count_set_bits()
中每次迭代结束时右移 n 的值来分析循环每次迭代中的最低有效位。然后，它调用函数
is_prime()
来收集设置的位数是否为素数。
输出
时空分析
时间复杂度：O(log(n) + sqrt(count))
。在函数
count_set_bits()
中，当我们逐位分析数字时，循环会执行 log(n) 次。函数 is_prime() 需要 O(sqrt(count)) 时间来检查 count 是否为素数。这两个函数在执行过程中都会被调用一次。
空间复杂度：O(1)
，因为在实现中没有使用任何辅助空间。无论输入数字的大小，该算法始终使用恒定的空间。
结论
有害数字是一个有趣的数学概念，可以使用上面讨论的方法轻松有效地识别它们。本文还介绍了要使用的算法、C++ 程序解决方案以及时间和空间复杂度分析。
Input: 37
Output: Pernicious
Input: 22
Output: Pernicious
Input: 71
Output: Not Pernicious
Input: 64
Output: Not Pernicious
#include
using namespace std;
// this function counts the number of set bits by analyzing the rightmost bit using a while loop till n > 0.
// it performs logical & operation between 1 and n to determine if the rightmost bit is set or not.
// if it is set, count is incremented by 1
// right shift the value of n to make the bit left of the rightmost bit, the new rightmost bit.
int count_set_bits(int n){
int count = 0;
while (n > 0){
// if the rightmost bit is 1: increment count
if ((n & 1) > 0){
count++;
}
// right shift the value of n to examine the next least significant bit
n = n >> 1;
}
return count;
}
// this function determines if count of set bits in the given number is prime
bool is_prime(int count){
if (count < 2)
return false;
for (int i = 2; i * i < count; i++){
if (count % i == 0)
return false;
}
return true;
}
// this functions states if count of set bits is prime -> pernicious
bool is_pernicious(int n){
int count;
count = count_set_bits(n);
// if count is prime return true
if (is_prime(count)){
return true;
}
return false;
}
// main function
int main(){
int n = 11;
if (is_pernicious(n)){
cout << n <<" is Pernicious Number";
}
else{
cout << n << " is Non-Pernicious Number";
}
return 0;
}
11 is Pernicious Number