数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学布鲁姆整数
问题陈述包括检查给定的数字（将作为用户输入），判断其是否为布鲁姆数。
布鲁姆整数是一个半素数，其不同的素因子 a 和 b 的形式为 4t+3，其中 t 为某个正整数。半素数是一个恰好是两个素数的乘积的数，或者是一个恰好有两个素数因子的自然数。在半素数的情况下，因子可以相等。
如果任何数字 N 是布鲁姆整数，它必须只有两个因子（除了 1 和数字本身），这两个因子 a 和 b 必须是不同的素数，其形式为 4t+3（对于任何正整数 t）。
前几个布鲁姆整数是 21, 33, 57, 69, 77, 93, 129, 133, 141……
任何偶数都不能是布鲁姆整数，因为两个形式为 4t+3（即奇数）的不同素数的乘积将始终是一个大于 20 的奇数。
在这个问题中，我们将得到一个数字 N，我们需要检查这个数字是否为布鲁姆整数。
示例
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 是布鲁姆整数。
INPUT : N=49 OUTPUT : No
解释：给定的数字是 49，可以表示为 7*7。由于 7 是素数，但对于一个数要成为布鲁姆整数，它应该是两个不同素数的乘积。因此，49 不是布鲁姆整数。
INPUT : N=35 OUTPUT : No
解释：数字 35 可以表示为 7 和 5 的乘积（即 7*5）。这两个数字都是不同的素数，7 具有 4t+3 的形式，但 5 对于任何整数 t 值都不能表示为 4t+3。因此，35 不是布鲁姆整数。
让我们了解如何检查一个数是否为布鲁姆整数的算法。
算法
要检查一个数是否为布鲁姆整数，我们可以简单地找到直到该数的所有素数，然后检查两个形式为 4t+3 的不同素数的乘积是否可以构成给定的数。
我们将使用埃拉托斯特尼筛法的概念来找到直到给定数字 N 的所有素数。埃拉托斯特尼筛法是找到直到任何给定数字的所有素数的最有效方法。
在这个方法中，我们将创建一个大小为 N+1 的布尔数组，其中 N 将是给定的数字。如果该数字是素数，我们将在等于该数字的索引值处存储 true，否则我们将在数组中存储 false。
为了更新直到 N 的非素数的对应索引值的 false，我们将从 i=2 到 i<=sqrt(N) 迭代一个 for 循环，因为任何小于或等于 N 的数，如果它不是素数，则必须有一个因子位于 [2, sqrt(N)] 范围内。
如果 arr[i] 为 true（对应于 i 的值），我们将从 p=i*i 到 p<=N 迭代一个嵌套循环，并在 p 的所有后续倍数处更新为 false。如果 i 的对应值为 false，我们将迭代 i 的下一个值。
使用埃拉托斯特尼筛法，我们可以得到从 1 到 N 的所有素数。现在，在数组中迭代一个 for 循环，我们将检查是否存在任何素数是给定数字 N 的因子，并且具有 4t+3 的形式，并且 N 除以该素数的商也是一个具有 4t+3 形式的不同素数。如果满足上述所有条件，则给定的数字 N 将是布鲁姆整数，否则就不是。
我们将在这个方法中使用这个算法来有效地解决这个问题。
方法
在我们的方法中实现算法以检查 N 是否为布鲁姆整数的步骤如下：
我们将创建一个函数来检查一个数是否为布鲁姆整数。
在函数中，使用埃拉托斯特尼筛法的概念，我们将在大小为 N+1 的布尔数组中，为直到 N 的所有素数存储 true（在对应的索引处）。
从 i=2 到 i<=N 迭代一个 for 循环，以检查是否存在任何形式为 4t+3 的素数是给定数字的因子。
如果我们找到任何是 N 的因子并且具有 4t+3 形式的素数，我们将存储 N 除以该素数的商。
如果商也是素数并且具有 4t+3 的形式，我们将返回 true，否则我们将返回 false。
如果函数返回 true，则该数字是布鲁姆整数。
示例
该方法的 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 的数组来存储素数。
结论
本文讨论了布鲁姆整数的概念。在本文中，我们提出了一种有效的方法，使用 C++ 中埃拉托斯特尼筛法的概念来检查一个数是否为布鲁姆整数。
我希望在阅读本文后，您已经弄清楚了布鲁姆整数的概念，并理解了如何检查一个数是否为布鲁姆整数的方法。
241 次浏览
