Pernicious Number In C++

In this article, we will discuss the Pernicious Number in C++.

What is the Pernicious Number?

If a number is positive and the number of set bits in its binary expansion is prime , that number is considered a Pernicious number. 3 is the first pernicious number because it equals (11) 2. There are two set bits, where 2 is a prime number in the binary representation of three.

The first ten pernicious numbers are: 3, 5, 6, 7, 9, 10, 11, 12, 13, 14 .

Properties:

• ✅ Any number that is in the power of two is not a pernicious number because a power of two is denoted by a 1 followed by zeroes in binary representation. It being said, 1 is not regarded as a prime number.
• ✅ As there are two ones in binary form which is prime, any number in the form 2^n + 1 with n > 0 is pernicious.
• ✅ A pernicious number called a Mersenne number is one of the following: 2^p - 1 with prime p.

For Example:

Input:

Output:

• ✅ Pernicious Number.
• ✅ Binary Expansion: 1100
• ✅ Here there are 2 set bits, and 2 is a prime number.
• ✅ Hence, 12 is a pernicious number.

Input:

Output:

• ✅ Pernicious Number.
• ✅ Binary Expansion: 10101
• ✅ Here there are 3 set bits, and 3 is a prime number.
• ✅ Hence, 21 is a pernicious number.

Input:

Output:

• ✅ Not a Pernicious Number.
• ✅ Binary Expansion: 100000 (2^5).
• ✅ Here there is only one set bit, and 1 is not a prime number.
• ✅ 32 is not a prime number.

Example:

Let us take a C++ Program to check whether the given number is a pernicious number or not:-

#include<iostream>
#include<cmath>
using namespace std;
// Function to count the number of set bits (ones) in a binary representation
int countSetBits(int n) {
    int count = 0;
    while (n) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}
// Function to check if a number is a prime number or not prime
bool isPrime(int n) {
    if (n <= 1)
        return false;
    if (n <= 3)
        return true;
    if (n % 2 == 0 || n % 3 == 0)
        return false;
  for(int i=5;i*i <=n ; i=i+6)
      if(n%i == 0 || n%(i+2)==0)
            return false;
    return true;
}
// Function to check if a number is pernicious
bool isPernicious(int n) {
    // Count the number of set bits (ones) in the binary representation of n
    int setBits = countSetBits(n);
    // Check if the count of set bits is a prime number or not
    return isPrime(setBits);
}
int main() {
    int num;
    cout << "Enter a number: ";
    cin >> num;
    if (isPernicious(num))
        cout << num << " is a pernicious number." << endl;
    else
        cout << num << " is not a pernicious number." << endl;
    return 0;
}

Output:

Explanation:

Counting setBits (countSetBits):

• ✅ The countsetBits function will determine how many set bits are there in the binary representation of a number with a value of 1.
• ✅ This function iterates through every bit of integer and determines whether it is a set bit or not and increments count accordingly.
• ✅ The number can be efficiently shifted to the right to verify each bit until the number equals 0.
• ✅ The count of set bits is finally returned.

Checking for Primality (isPrime function):

• ✅ A number's prime factor can be calculated using this function.
• ✅ In order to address common instances first, it returns false if the number is less than or equal to 1. It returns true if the value is two or three.
• ✅ Next, it verifies the primality of any further numbers. It goes through all possible divisions of 5 up to the number's square root.
• ✅ It determines if a given number is divisible by its next odd neighbor (i + 2) or by its current divisor (i). If so, false is returned.
• ✅ It returns true if no divisors are discovered, meaning the number is prime.

Checking for Perniciousness (isPernicious function):

• ✅ This function verifies if a given number is a pernicious number or not.
• ✅ Using the countSetBits function, it first determines the number of set bits in the binary representation of the input number.
• ✅ After that, the isPrime function is used to determine whether this count is a prime number.
• ✅ It returns true if the count of set bits is prime, meaning that the number is pernicious. Otherwise, it returns false.

Complexity Analysis:

Time Complexity:

• ✅ The time complexity to find whether a given number is pernicious or not is O(log n + sqrt(n)).

Space Complexity:

• ✅ The space complexity to find whether a given number is pernicious or not is O(1) because no auxiliary space is used.