如果數字是正整數且其二進位展開中的設定位數是質數，則該數字被認為是有害的。第一個有害數字是 3，因為 3 = (11)2。可以看出3的二進位表示的設定位數為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 = 26，即它是2的冪，它有1個設定位。由於1不是質數，64不是一個惡性數。
我們必須知道設定位數是否為質數，以便確定一個數是否是惡性的。手頭上的主要任務是計算該數的二進制展開中的設定位數。以下方法可用於計算設定位數，然後確定結果是否為質數。
該方法包括以下步驟 -
使用迴圈和右移運算子迭代數字的所有位元。
如果位元值為 1，則設定位元的計數加 1。
檢查計數的最終值是否為質數。
顯示答案。
函數 is_prime()
如果 (n < 2)< 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 << “非有害數字”
列印輸出
程式使用函數
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)，因為實作中沒有使用任何輔助空間。無論輸入數字的大小，演算法始終使用恆定的空間。
有害數字是一個有趣的數學概念，可以使用上面討論的方法輕鬆有效地識別它們。本文也介紹了要使用的演算法、C 程式解決方案以及時間和空間複雜度分析。
以上是有害數字的詳細內容。更多資訊請關注PHP中文網其他相關文章！
