Trusted answers to developer questions
What are pernicious numbers?
Ravi
Overview
A pernicious number is a positive number whose count of set bits in its binary form is prime. All powers of 2 are not pernicious numbers because the number of set bits in such numbers is 1 and 1 is not a prime number.
For example, 3 is a pernicious number, as the number of set bits in it is 2.
Given a number n, find out whether it’s a pernicious number or not.
Example 1:
- Input:
n = 5 - Output:
5is a pernicious number.
Example 2:
- Input:
n = 15 - Output:
15is not a pernicious number.
Solution
The solution is quite straightforward. These are the steps we follow to figure out the solution:
- We find the count of set bits in the given number.
- We check whether the count of set bits obtained from step 1 is a prime number or not.
For step 1, refer to the How to find the number of set bits in an integer shot.
For step 2, refer to the How do you check if a number is prime in Python? shot.
Example
def countSetBits(n):
count = 0
while n:
n = n & (n - 1)
count+=1
return count
def isPrime(inp):
if inp == 1: return False
for n in range(2,int(inp**0.5)+1):
if inp % n==0:
return False
return True
n = 15
set_bit_count = countSetBits(n)
if isPrime(set_bit_count):
print(n, " is a pernicious number")
else:
print(n, " is not a pernicious number")Explanation
- Lines 1–6: We define a function called
countSetBitsthat calculates the number of set bits in a given number. - Lines 8–14: We define a function called
isPrimethat states whether a given number is a prime number or not. - Line 17: We define the number
nthat we want to check. - Line 18: We invoke the
countSetBits()function withnas the number and get the number of set bits inn. - Lines 19–22: We check whether the result in line 18 is a prime number or not by invoking the
isPrimefunction. Then, we print the result to the console.
RELATED TAGS
bitwise
CONTRIBUTOR
Ravi
RELATED COURSES
View all Courses
Keep Exploring
Related Courses
SOLUTIONS
SOLUTIONS
SOLUTIONS
