布魯姆整數

問題陳述包括檢查將作為使用者輸入的給定數字，如果它是 Blum 數字。

A Blum 整數 是一個半質數，其不同質數因子 a 和 b 的形式為 4t 3，其中 t 是某個正整數。半質數是恰好兩個質數的乘積的數，或恰好具有兩個質數因數的自然數。對於半素數，因子可能相等。

如果任何數字N 是一個blum 整數，它必須只有兩個因子，例如N=a*b，而不是1 和數字本身以及兩個因子，a 和b 必須是不同的素數形式4t 3（對於任何正整數t）。

前幾個blum整數是21, 33, 57, 69, 77, 93, 129, 133, 141…

#任何偶數自然數都不能是模糊整數，因為兩個不同質因數的乘積（形式為 4t 3（即奇數））將永遠是大於 20 的奇數。

在這個問題中，我們將得到一個數字 N，我們需要檢查該數字是否為 blum 整數。

範例

INPUT : N=57
OUTPUT : yes

說明：輸入中給出的數字是 57。數字 57 可以是表示為 19 和 3 的乘積（即 19*3）。由於這兩個因子都是不同的質數，且形式為 4t 3。

19=4*4 3，本例中t的值為4。

3=4*0 3，t的值為0。

因此，數字 57 是一個 blum 整數。

INPUT : N=49
OUTPUT : No

說明：給出的數字是 49，可以表示為 7*7。因為 7 是一個質數，但對於一個數字來說，它應該是兩個不同質數的乘積。因此，49 不是一個模糊整數。

INPUT : N=35
OUTPUT : No

說明：數字 35 可以表示為 7 和 5 的乘積（即7*5）。這兩個數字都是不同的質數，7 的形式為 4t 3，但對於 t 的任何整數值，5 都不能表示為 4t 3。因此，35 不是一個模糊的整數。

讓我們了解演算法，以檢查該數字是否為 blum 整數。

演算法

要檢查該數字是否為 blum 整數，我們可以簡單地找到該數字之前的所有質數，然後檢查 4t 3 形式的兩個不同質數的乘積是否可以組成給定的數字。

我們將使用埃拉托斯特尼篩法的概念來找出直到給定數字 N 的所有質數。埃拉托斯特尼篩法是查找任意給定數字 N 之前的素數的最有效方法數量。

• 在此方法中，我們將建立一個大小為 N 1 的布林數組，其中 N 是給定的數字。如果該數字是索引值等於該數字的質數，我們將儲存 true，否則我們將在陣列中儲存 false。

• 要更新非素數對應的索引值false 直到N，我們將在for 迴圈中從i=2 迭代到i

• 如果arr[i] 對應到i 的值是true，我們將在巢狀循環中從p=i*i 迭代直到p

使用埃拉托色尼篩，我們可以得到從 1 到 N 的所有質數。現在，在數組中的for 循環中迭代，我們將檢查是否存在任何素數，它是給定數字N 的因子，並且的形式為4t 3，並且素數除以N 的商也是形式為4t 3 的不同素數。如果滿足上述所有條件，則給定的數字 N 將是一個 blum 整數，否則不是。

我們將在我們的方法中使用該演算法，以便有效地解決問題。

方法

下面給出了在我們的方法中實作演算法來檢查 N 是否為 blum 整數的步驟 -

• 我們將建立一個函數來檢查該數字是否為 blum 整數。

• 在函數中，使用埃拉托斯特尼篩的概念，我們將所有質數的 true 儲存在大小為 N 1 的布林數組中，直到對應索引處的 N 為止。

• 在 for 迴圈中從 i=2 迭代到 i

• 如果我們找到任何質數，它是 N 的因子，且形式為 4t 3，我們將儲存 N 除以該質數的商數。

• 如果商數也是質數且形式為 4t 3，我們將傳回 true，否則傳回 false。

• 如果函數傳回 true，則該數字是一個 blum 整數。

範例

該方法的 C 程式碼 -

// C++ program to check if the number is a blum integer or not
#include <bits/stdc++.h>

using namespace std;

// to check if N is a blum integer or not
bool check(int N){
   bool a[N + 1]; //to store true corresponding to the index value equal to prime number
    memset(a,true,sizeof(a));

   // to update the array with false at index value corresponding to non prime numbers
   for (int i = 2; i<=sqrt(N); i++) {

      //if i is a prime number
      if (a[i] == true) {

         //updating false at all the multiples of i less than or equal to N from i*i
         for (int p = i * i; p <= N; p += i)
            a[p] = false;
      }
   }

   //to check if there exist distinct prime numbers whose product is equal to N
   for (int i = 2; i <= N; i++) {
      if (a[i]) {

          //if i is the prime factor of the form 4t+3
         if ((N % i == 0) && ((i - 3) % 4) == 0) {
            int quotient = N / i;
            //to check if quotient*i=N and both are distinct prime numbers of form 4t+3
            if(quotient!=i && a[quotient] && (quotient-3)%4==0){
                return true;
            } else {
               return false;
            }
         }
      }
   }
   return false;
}
int main(){
   
   int N;
   N=469;
   //calling the function
   if (check(N)==true) //if function returns true, it is a blum integer
      cout <<N<<" is a blum integer."<<endl;
   else
      cout <<N<<" is not a blum integer."<<endl;
   return 0;
}

輸出

469 is a blum integer.

時間複雜度：O(N*log(log(N))，因為它是埃拉托斯特尼篩的時間複雜度。

空間複雜度：O(N)，因為我們使用大小為 N 1 的陣列來儲存素數。

結論

文章中討論了 blum 整數的概念。在本文中，我們使用 C 中的埃拉托色尼篩的概念提出了一種有效的方法來檢查數字是否為 blum 整數。

希望您在閱讀本文後已經清楚了 blum 整數的概念，並了解了檢查該數字是否為 blum 整數的方法。

以上是布魯姆整數的詳細內容。更多資訊請關注PHP中文網其他相關文章！