有害数

算法数学包括编程关键词：有害数
281 2023-08-30

如果数字是正整数并且其二进制展开中的设置位数是素数，则该数字被认为是有害的。第一个有害数字是 3，因为 3 = (11)₂。可以看出3的二进制表示的设定位数为2，是一个素数。

前10个有害数字是3、5、6、7、9、10、11、12、13、14。有趣的是，2的幂永远不可能是有害数字，因为它们总是只有1个设置位。1不是质数。另一方面，所有可以表示为2ⁿ + 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 = 2⁶，即它是2的幂，它有1个设置位。由于1不是质数，64不是一个恶性数。

解决方案

我们必须知道设置位数是否为质数，以便确定一个数是否是恶性的。手头的主要任务是计算该数的二进制展开中的设置位数。以下方法可用于计算设置位数，然后确定结果是否为质数。

该方法包括以下步骤 -

使用循环和右移运算符迭代数字的所有位。
如果位值为 1，则设置位的计数加 1。
检查计数的最终值是否为质数。
显示答案。

算法

函数 is_prime()

如果 (n < 2)

返回错误

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 <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)，因为在实现中没有使用任何辅助空间。无论输入数字的大小，该算法始终使用恒定的空间。