harmful number

#A number is considered harmful if it is a positive integer and the set number of digits in its binary expansion is a prime number. The first harmful number is 3 because 3 = (11)₂. It can be seen that the binary representation of 3 has a set number of digits of 2, which is a prime number.

The top 10 harmful numbers are 3, 5, 6, 7, 9, 10, 11, 12, 13, and 14. Interestingly, powers of 2 can never be harmful numbers because they always only have 1 bit set. 1 is not a prime number. On the other hand, all numbers that can be represented as 2ⁿ1, where n is any natural number, will always be bad numbers because they will have 2 set bits, and we know that 2 is a prime number.

Keeping in mind the properties of these harmful numbers, the following article discusses a way to check whether a number is harmful.

Problem Statement

This question aims to check whether the given number n is a harmful number, i.e. it is a positive number with a prime number of set bits in its binary expansion.

Example

Input: 37

Output: Pernicious

The translation of

Explanation

is:

Explanation

37 = Binary representation of 100101.

Set the number of digits = 3

Since 3 is a prime number, 37 is a bad number.

Input: 22

Output: Pernicious

The translation of

Explanation

is:

Explanation

22 = Binary representation of 10110.

Set number of digits = 3.

Since 3 is a prime number, 22 is a vicious number.

Input: 71

Output: Not Pernicious

The translation of

Explanation

is:

Explanation

The binary representation of

71 is 1000111.

Set number of digits = 4.

Since 4 is not a prime number, 71 is not a harmful number either.

Input: 64

Output: Not Pernicious

The translation of

Explanation

is:

Explanation

The binary representation of

64 is 1000000.

Set number of digits = 1.

Since 64 = 2⁶, i.e. it is a power of 2, it has 1 set bit. Since 1 is not a prime number, 64 is not a vicious number.

solution

We must know whether the set number of digits is a prime number in order to determine whether a number is malicious. The main task at hand is to calculate the set number of digits in the binary expansion of this number. The following method can be used to calculate a set number of digits and then determine whether the result is a prime number.

This method includes the following steps -

• Iterate over all bits of a number using loop and right shift operators.

• If the bit value is 1, the count of the set bit is increased by 1.

• Check whether the final value of the count is a prime number.

• Show answer.

algorithm

Function is_prime()

• If (n

Return error

• for (i from 2 to √a)

If (a%i==0)

Return error

• Return true

Function count_set_bits()

• Initialization counter = 0

• When (n > 0)

• If ((n & 1) > 0)

• Counter = Counter 1

• n = n >> 1

• Return Counter

Function is_pernious()

• Initialize counter

• Counter = count_set_bits(n)

• if (is_prime(counter) == true)

return true

• other

Return error

Function main()

• Initialize n

• if (is_pernious())

cout

• other

cout

• Print output

Example: C program

The program uses the function

is_pernicious()

to determine whether a number is pernicious. It analyzes the least significant bits in each iteration of the loop by right shifting the value by n at the end of each iteration in the function

count_set_bits()

. Then, it calls the function

is_prime()

to collect whether the set number of digits is a prime number.

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

Output

11 is Pernicious Number

Space-time analysis

Time complexity: O(log(n) sqrt(count)). In the function count_set_bits(), the loop executes log(n) times as we analyze the number bit by bit. The function is_prime() takes O(sqrt(count)) time to check whether count is prime. Both functions will be called once during execution.

Space complexity: O(1), because no auxiliary space is used in the implementation. Regardless of the size of the input number, the algorithm always uses a constant amount of space.

in conclusion

Harmful numbers are an interesting mathematical concept and they can be easily and effectively identified using the methods discussed above. This article also describes the algorithm to be used, a C program solution, and time and space complexity analysis.

The above is the detailed content of harmful number. For more information, please follow other related articles on the PHP Chinese website!