有害数

---

如果一个正整数的二进制展开式中1的个数是素数，则该数被称为有害数。第一个有害数是3，因为3 = (11)₂。可以看出，3的二进制表示中1的个数是2，这是一个素数。

前10个有害数是3、5、6、7、9、10、11、12、13、14。有趣的是，2的幂永远不可能是有害数，因为它们只有一个1。1不是素数。另一方面，所有可以表示为2ⁿ + 1的数（其中n是任意自然数）都将是有害数，因为它们将有两个1，而我们知道2是素数。

记住有害数的这些性质，以下文章讨论了一种检查一个数是否是有害数的方法。

问题陈述

这个问题旨在检查给定的数n是否是有害数，即它是一个正数，其二进制展开式中1的个数是素数。

示例

Input: 37

Output: Pernicious

解释

37的二进制表示为100101。

1的个数 = 3

由于3是素数，37是有害数。

Input: 22

Output: Pernicious

解释

22的二进制表示为10110。

1的个数 = 3。

由于3是素数，22是有害数。

Input: 71

Output: Not Pernicious

解释

71的二进制表示为1000111。

1的个数 = 4。

由于4不是素数，71不是有害数。

Input: 64

Output: Not Pernicious

解释

64的二进制表示为1000000。

1的个数 = 1。

由于64 = 2⁶，即它是2的幂，它只有一个1。由于1不是素数，64不是有害数。

解决方案方法

为了确定一个数是否是有害数，我们必须知道1的个数是否是素数。手头的主要任务是计算该数二进制展开式中1的个数。可以使用以下方法来计算1的个数，然后确定结果是否是素数。

该方法包括以下步骤：

• 使用循环和右移运算符迭代遍历数字的所有位。

• 如果位值为1，则将1的个数加一。

• 检查最终的计数是否为素数。

• 显示答案。

算法

函数 is_prime()

• if (n < 2)

return false

• for (i from 2 to √a)

if (a % i == 0)

return false

• return true

函数 count_set_bits()

• 初始化计数器 = 0

• while (n > 0)

• if ((n & 1) > 0)

• counter = counter + 1

• n = n >> 1

• return counter

函数 is_pernicious()

• 初始化计数器

• counter = count_set_bits(n)

• if (is_prime(counter) == true)

return true

• else

return false

函数 main()

• 初始化 n

• if (is_pernicious())

cout << “有害数”

• else

cout << “非有害数”

• 打印输出

示例：C++程序

该程序使用函数is_pernicious()来确定一个数是否是有害数。

is_pernicious()

。它通过在函数count_set_bits()中每次迭代结束时右移n的值，来分析每次迭代中最不重要的位。

count_set_bits()

。然后它调用函数

is_prime()

来收集1的个数是否为素数。

#include <iostream>
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

时间和空间分析

时间复杂度：O(log(n) + sqrt(count))。在函数count_set_bits()中，循环执行log(n)次，因为我们逐位分析数字。函数is_prime()需要O(sqrt(count))的时间来检查count是否为素数。这两个函数在执行过程中都只调用一次。

空间复杂度：O(1)，因为实现中没有使用辅助空间。无论输入数字如何，算法始终使用恒定的空间。

结论

有害数是一个有趣的数学概念，可以使用上述方法轻松有效地识别它们。本文还介绍了要使用的算法、C++程序解决方案以及时间和空间复杂度分析。