问题陈述包括检查将作为用户输入的给定数字，如果它是 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 整数的方法。
