在將給定的二進制數轉換為L到R之間的進制後，計算質數的個數

標題「在L 和R 之間轉換給定二進制數後的質數計數」是指一個數學問題，涉及將二進制數轉換為L 和R 之間的基數，然後計算來自L 和R 之間的質數的個數。轉換。在數學中，質數是大於 1 的整數，只能被 1 和它本身整除。

要將二進位數轉換為不同基數的數，需要將該數寫成不同的數位。數制的基數是唯一的數字數量，轉換是透過在新基數中找到該數的等效表示來完成的。在轉換之後計算質數是一個困難的數論問題，它在密碼學、電腦科學和其他領域中有用途。要解決這個問題，你需要對數論、質數和數制有很多了解。

什麼是質數？

只有當一個數能被 1 和該數本身整除時，該數才稱為質數。舉個例子，數字 5 是質數，因為它只能被數字 1 和 5 整除，而 6 不是質數，因為它也能被 2 和 3 整除。

素數的數量只是詢問在給定的一組數字中有多少個質數。例如，取一組數字{1,2,3,4,5,6,7,8,9}，在這組數字中，質數的數目是4，它們是2、3、5、7。此外，1不是質數，因為它的唯一正因子是1本身。

方法

有兩種主要方法來計算質數問題，如下所示−

• 暴力方法

• 質因數分解

#演算法

步驟 1 - 輸入二進位數以及基數 L 和 R 的範圍。

步驟 2 - 迭代 L 和 R（包括）之間的每個鹼基。

第 3 步 - 將二進位數轉換為目前基數。

步驟 4 − 檢查轉換後的數字是否為質數。

步驟5 - 如果轉換後的數字是質數，則將質數計數增加1。

步驟 6 - 重複步驟 3-5，針對範圍 L 到 R 中的所有基數。

步驟 7 − 傳回所得的質數的總數。

下面給出的是演算法的偽代碼 -

input: binary number b, range of bases L and R
output: count of prime numbers in the given range

Number_of_prime = 0
for base = L to R
convert b to base
if number_is_prime(converted_number)
   Number_of_prime ++
return Number_of_prime

number_is_prime() 是一個方法，它接受一個數字作為輸入，並傳回一個布林值，顯示該數字是否為質數。

方法一：暴力解決方法

Brute Force Approach（蠻力法）涉及將二進制數轉換為從L到R之間的每個進制，併計算每個轉換中的質數數量。對於較大的數字，需要檢查所有可能的變化，這可能會耗費大量時間。

下面的程式碼包含三個函數。第一個函數是“isPrime”，如果輸入數字是質數，則傳回 1，否則傳回 0。第二個函數「binaryToDecimal」將二進制數轉換為十進制數。第三個函數「countPrimes」計算透過將輸入範圍之間的二進位數轉換為十進位數所獲得的質數的數量。最後，主函數輸入二進位數和一個數字範圍，呼叫「countPrimes」函數並列印素數的計數。

Example

的中文翻譯為：

範例

這段程式碼為二進制數和範圍L和R提供了預先定義的值。在這個例子中，我使用了二進制數1010和範圍5到20。您可以根據需要在主函數中更改這些值。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

// Function to check if a number is prime or not
int isPrime(int n) {
   int i;
   for(i = 2; i <= sqrt(n); i++) {
      if(n%i == 0) {
         return 0;
      }
   }
   return 1;
}

// Function to convert binary to decimal
int binaryToDecimal(int n) {
   int decimal = 0, i = 0, remainder;
   while(n != 0) {
      remainder = n % 10;
      n /= 10;
      decimal += remainder * pow(2, i);
      ++i;
   }
   return decimal;
}

// Function to count primes in a given range
int countPrimes(int L, int R) {
   int count = 0, i;
   for(i = L; i <= R; i++) {
      int decimal = binaryToDecimal(i);
      if(isPrime(decimal)) {
         count++;
      }
   }
   return count;
}

// Main function
int main() {
   int binary = 1010; // Example binary number
   int L = 5;         // Example range lower limit
   int R = 20;        // Example range upper limit

   // Count primes and print result
   int count = countPrimes(L, R);
   printf("Number of primes after converting %d to base between %d and %d is: %d\n", binary, L, R, count);

   return 0;
}

輸出

Number of primes after converting 1010 to base between 5 and 20 is: 7

方法 2：質因數分解

素數分解包括尋找變換後的數的素數因子並檢查它們是否在素數範圍內。對於較小的數字來說，它可能是一種有效的方法，但對於較大的數字來說，計算成本可能會很高。

下面的程式碼定義了兩個函數 isPrime() 和 countPrimes()，它們檢查給定數字是否為質數或計算給定數字之前的質數個數。主函數接受使用者輸入的二進制數和基數限制，將二進制數轉換為十進制，然後將其轉換為給定限制內的不同基數。對於每次轉換，程式都會尋找質因數，如果它們在當前基本限制內，則增加計數器。最後，程式列印找到的素數的數量。此程式碼導入標準輸入/輸出和布林庫。

Code

的中文翻譯為：

程式碼

#include <stdio.h>
#include <stdbool.h>
#include <math.h>

bool isPrime(int n) {
   if (n <= 1) {
      return false;
   }
   int i;
   for (i = 2; i <= sqrt(n); i++) {
      if (n % i == 0) {
         return false;
      }
   }
   return true;
}

int main() {
   int binaryNum = 110101; // Predefined binary number input
   int L = 3; // Predefined lower limit of base
   int R = 6; // Predefined upper limit of base

   int decimalNum = 0, base = 1;
   while (binaryNum > 0) {
      int digit = binaryNum % 10;
      decimalNum += digit * base;
      base *= 2;
      binaryNum <span>/</span>= 10;
   }

   int transformedNum, factor;
   int primeCount = 0;
   for (int baseNum = L; baseNum <= R; baseNum++) {
      transformedNum = decimalNum;
      while (transformedNum > 1) {
         for (int i = 2; i <= transformedNum; i++) {
            if (transformedNum % i == 0) {
               factor = i;
               break;
            }
         }
         transformedNum <span>/</span>= factor;
         if (isPrime(factor) && factor >= baseNum) {
            primeCount++;
         }
      }
   }
   printf("Count of primes after converting the given binary number in base between L to R is: %d", primeCount);
   return 0;
}

輸出

Count of primes after converting the given binary number in base between L to R is: 4

結論

總而言之，我們可以先將給定的二進位數轉換為 L 到 R 之間的基數，然後計算該範圍內的質數個數，來確定質數的個數。

以上是在將給定的二進制數轉換為L到R之間的進制後，計算質數的個數的詳細內容。更多資訊請關注PHP中文網其他相關文章！