Blum 整数
问题陈述包括检查将作为用户输入的给定数字是否为 Blum 数字。
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……
任何偶数自然数都不能是 blum 整数，因为两个不同的素因数的乘积形式为 4t+3(即奇数)，它们始终是大于 20 的奇数。
在这个问题中，我们将给出一个数字 N，我们需要检查该数字是否是 blum 整数或不是。
示例
输入:N=57 输出:yes
解释: 输入的数字是 57。57 这个数字可以表示为 19 和 3 的乘积(即 19*3)。由于两个因子都是不同的质数，并且形式为 4t+3。
19=4*4+3，在这种情况下，t 的值为 4。
3=4*0+3，t 的值为 0。
因此，数字 57 是一个 blum 整数。
输入:N=49 输出:No
解释:给出的数字是 49，可以表示为 7*7。因为 7 是质数，但对于一个数字来说，要成为 blum 整数，它应该是两个不同质数的乘积。因此，49 不是 blum 整数。
输入:N=35 输出:No
解释: 数字 35 可以表示为 7 和 5 的乘积(即 7*5)。这两个数字都是不同的素数，7 的形式为 4t+3，但对于任何整数值 t，5 都不能表示为 4t+3。因此，35 不是 blum 整数。
让我们了解算法，以检查数字是否为 blum 整数。
算法
要检查数字是否为 blum 整数，我们可以简单地找到直到该数字的所有素数，然后检查两个不同素数(形式为 4t+3)的乘积是否可以组成给定的数字。
我们将使用埃拉托斯特尼筛法的概念来查找直到给定数字 N 的所有素数。埃拉托斯特尼筛法是查找直到任何给定数字的素数的最有效方法。
在此方法中，我们将创建一个大小为 N+1 的布尔数组，其中 N 将是给定的数字。如果数字是素数，我们将在索引值等于数字的位置存储 true，否则我们将在数组中存储 false。
要更新索引值中与非素数对应的 false，直到 N，我们将在 for 循环中从 i=2 迭代到 i<=sqrt(N)，因为任何小于或等于 N 的数字，如果它不是素数，那么一定有一个因子在 [2, sqrt(N)] 范围内。
如果 arr[i] 对应于 i 的值是 true，我们将在嵌套循环中从 p=i*i 迭代直到 p<=N，并在 p 的所有下一个倍数处更新 false。如果在 i 的对应值处为 false，我们将迭代下一个 i 的值。
使用埃拉托斯特尼筛选法，我们可以得到从 1 到 N 的所有素数。现在，在数组中进行 for 循环迭代，我们将检查是否存在任何素数，它是给定数字 N 的因数，并且形式为 4t+3，并且该素数除以 N 的商也是形式为 4t+3 的不同素数。如果满足上述所有条件，则给定的数字 N 将是一个 blum 整数，否则则不是。
我们将在我们的方法中使用此算法来有效地解决问题。
方法
在我们的方法中，实现算法以检查 N 是否为 blum 整数的步骤如下 -
我们将创建一个函数来检查数字是否为 blum 整数。
在函数中，使用埃拉托斯特尼筛法的概念，我们将在大小为 N+1 的布尔数组中为相应索引处的所有素数存储 true，直到 N。
在 for 循环中从 i=2 迭代到 i<=N，以检查形式为 4t+3 的任何素数是否是给定数字的因数。
如果我们找到任何素数N 的因数，形式为 4t+3，我们将存储 N 除以该素数的商。
如果商也是素数，形式为 4t+3，我们将返回 true，否则我们将返回 false。
如果函数返回 true，则该数字为 blum 整数。
示例
该方法的 C++ 代码 −
// C++ 程序检查数字是否为 blum 整数
#include <bits/stdc++.h>
using namespace std;
// 检查 N 是否为 blum 整数
bool check(int N){
bool a[N + 1]; //存储对应于等于素数的索引值的 true
memset(a,true,sizeof(a));
// 使用对应于非素数的索引值处的 false 更新数组
for (int i = 2; i<=sqrt(N); i++) {
//如果 i 是素数
if (a[i] == true) {
//将 i*i 中所有小于或等于 N 的 i 的倍数更新为 false
for (int p = i * i; p <= N; p += i)
a[p] = false;
}
}
//检查是否存在乘积等于 N 的不同素数
for (int i = 2; i <= N; i++) {
if (a[i]) {
//如果 i 是 4t+3 形式的素因数
if ((N % i == 0) && ((i - 3) % 4) == 0) {
int quotient = N / i;
//检查商*i=N 并且两者都是 4t+3 形式的不同素数
if(quotient!=i && a[quotient] && (quotient-3)%4==0){
return true;
} else {
return false;
}
}
}
}
return false;
}
int main(){
int N;
N=469;
//调用函数
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 整数的概念。在本文中，我们提出了一种有效的方法来检查数字是否为 blum 整数，使用 C++ 中的埃拉托斯特尼筛法概念。
我希望您在阅读本文后已经明确了 blum 整数的概念，并理解了检查数字是否为 blum 整数的方法。
