如果数字是正整数并且其二进制展开中的设置位数是素数，则该数字被认为是有害的。第一个有害数字是 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
打印输出
示例：C++ 程序
程序使用函数
is_pernicious()
确定数字是否有害。它通过在函数
count_set_bits()
中每次迭代结束时右移 n 的值来分析循环每次迭代中的最低有效位。然后，它调用函数
is_prime()
来收集设置的位数是否为素数。
#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 primebool is_prime(int count){ if (count < 2) return false; for (int i = 2; i * i perniciousbool 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 functionint 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
时空分析
时间复杂度：O(log(n) + sqrt(count))。在函数 count_set_bits() 中，当我们逐位分析数字时，循环会执行 log(n) 次。函数 is_prime() 需要 O(sqrt(count)) 时间来检查 count 是否为素数。这两个函数在执行过程中都会被调用一次。
空间复杂度：O(1)，因为在实现中没有使用任何辅助空间。无论输入数字的大小，该算法始终使用恒定的空间。
结论
有害数字是一个有趣的数学概念，可以使用上面讨论的方法轻松有效地识别它们。本文还介绍了要使用的算法、C++ 程序解决方案以及时间和空间复杂度分析。
以上就是有害数的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1443391.html
微信扫一扫 
支付宝扫一扫 
