有害數字

如果數字是正整數且其二進位展開中的設定位數是質數，則該數字被認為是有害的。第一個有害數字是 3，因為 3 = (11)₂。可以看出3的二進位表示的設定位數為2，是一個質數。

前10個有害數字是3、5、6、7、9、10、11、12、13、14。有趣的是，2的冪永遠不可能是有害數字，因為它們總是只有1個設定位。 1不是質數。另一方面，所有可以表示為2ⁿ 1的數字，其中n是任意自然數，將始終是有害數字，因為它們將有2個設定位，而我們知道2是一個質數。

牢記這些有害數字的特性，以下的文章討論了一種檢查一個數字是否為有害數字的方法。

問題陳述

此問題旨在檢查給定數字 n 是否是一個有害數字，即它是一個正數，在其二進制展開中具有質數個設定位。

範例

Input: 37

Output: Pernicious

Explanation

的翻譯為：

解釋

37 = 100101 的二進位表示。

設定位數 = 3

由於 3 是質數，因此 37 是有害的數字。

Input: 22

Output: Pernicious

Explanation

的翻譯為：

解釋

22 = 10110 的二進位表示。

設定位數 = 3。

由於3是一個質數，22是一個惡毒數。

Input: 71

Output: Not Pernicious

Explanation

的翻譯為：

解釋

71的二進位表示為1000111。

設定位數 = 4。

由於 4 不是質數，因此 71 也不是有害數字。

Input: 64

Output: Not Pernicious

Explanation

的翻譯為：

解釋

64的二進位表示為1000000。

設定位數 = 1。

由於64 = 2⁶，即它是2的冪，它有1個設定位。由於1不是質數，64不是一個惡性數。

解決方案

我們必須知道設定位數是否為質數，以便確定一個數是否是惡性的。手頭上的主要任務是計算該數的二進制展開中的設定位數。以下方法可用於計算設定位數，然後確定結果是否為質數。

該方法包括以下步驟 -

• 使用迴圈和右移運算子迭代數字的所有位元。

• 如果位元值為 1，則設定位元的計數加 1。

• 檢查計數的最終值是否為質數。

• 顯示答案。

演算法

函數 is_prime()

• 如果 (n

回傳錯誤

• 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

• 列印輸出

範例：C 程式

程式使用函數

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中文網其他相關文章！