如果数字是正整数并且其二进制展开中的设置位数是素数，则该数字被认为是有害的。第一个有害数字是 3，因为 3 = (11)2。可以看出3的二进制表示的设定位数为2，是一个素数。
前10个有害数字是3、5、6、7、9、10、11、12、13、14。有趣的是，2的幂永远不可能是有害数字，因为它们总是只有1个设置位。1不是质数。另一方面，所有可以表示为2n + 1的数字，其中n是任意自然数，将始终是有害数字，因为它们将有2个设置位，而我们知道2是一个质数。
牢记这些有害数字的特性，下面的文章讨论了一种检查一个数字是否为有害数字的方法。
问题陈述
此问题旨在检查给定数字 n 是否是一个有害数字，即它是一个正数，在其二进制展开中具有质数个设置位。
示例
Input: 37
登录后复制
Output: Pernicious
登录后复制登录后复制
Explanation
的翻译为：
解释
37 = 100101 的二进制表示。
设置位数 = 3
由于 3 是素数，因此 37 是一个有害的数字。
Input: 22
登录后复制
Output: Pernicious
登录后复制登录后复制
Explanation
的翻译为：
解释
22 = 10110 的二进制表示。
设置位数 = 3。
由于3是一个质数，22是一个恶毒数。
Input: 71
登录后复制
Output: Not Pernicious
登录后复制登录后复制
Explanation
的翻译为：
解释
71的二进制表示为1000111。
设置位数 = 4。
由于 4 不是质数，因此 71 也不是有害数字。
Input: 64
登录后复制
Output: Not Pernicious
登录后复制登录后复制
Explanation
的翻译为：
解释
64的二进制表示为1000000。
设置位数 = 1。
由于64 = 26，即它是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 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 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
