C++ 卑劣数

如果一个正整数的二进制表示中设置的位数是质数，则称该数为卑劣数。第一个有害数是3，因为3 = (11)2。可以看到，3的二进制表示中设置的位数是2，而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

解释

37的二进制表示为100101。

设置位数 = 3

因为3是一个质数，所以37是一个恶毒数。

Input: 22

Output: Pernicious

解释

22的二进制表示为10110。

设置的位数为3。

由于3是一个质数，所以22是一个恶毒数。

Input: 71

Output: Not Pernicious

解释

71的二进制表示为1000111。

设置的位数=4。

由于4不是一个质数，所以71不是一个恶性数。

Input: 64

Output: Not Pernicious

解释

64的二进制表示为1000000。

设置位的数量= 1。

由于64 = 2的6次方，即它是2的幂，它具有1个设置位。由于1不是质数，64不是一个危险数字。

解决方案

我们必须知道设置位的数量是否为质数，以便决定一个数字是否是危险的。手头的主要任务是计算数字的二进制表示中设置位的数量。可以使用以下方法来计算设置位并确定结果是否为质数。

该方法包括以下步骤−

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

步骤

函数is_prime()

如果 (n < 2)

返回false

对于 (i从2到√a)

如果 (a % i 0)

返回false

返回true

函数count_set_bits()

初始化counter = 0
while (n > 0)
如果 ((n & 1) > 0)
counter = counter + 1
n = n >> 1
返回counter

函数is_pernicious()

初始化counter
counter = count_set_bits(n)
如果 (is_prime(counter) true)

返回true

else

返回false

函数main()

初始化n
如果 (is_pernicious())

cout << “危险数字”

else

cout << “非吉利数”

打印输出

示例：C++程序

该程序使用以下函数判断一个数是否为吉利数：

is_pernicious()

count_set_bits()

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;
}