布鲁姆整数

问题陈述包括检查将作为用户输入的给定数字，如果它是 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中文网其他相关文章！