bloom integer

The problem statement consists of checking a given number that will be entered as user input if it is a Blum number.

A Blum Integer is a semiprime number whose distinct prime factors a and b are of the form 4t 3, where t is some positive integer. A semiprime is a number that is the product of exactly two prime numbers, or a natural number that has exactly two prime factors. For semiprimes, the factors may be equal.

If any number N is a blum integer, it must have only two factors, such as N=a*b, instead of 1 and the number itself and the two factors, a and b must be of different prime form 4t 3 (for any positive integer t).

The first few blum integers are 21, 33, 57, 69, 77, 93, 129, 133, 141......

No even natural number can be a fuzzy integer because the product of two non-prime factors (of the form 4t 3 (i.e. an odd number)) will always be an odd number greater than 20.

In this problem, we will be given a number N and we need to check if the number is a blum integer.

Example

INPUT : N=57
OUTPUT : yes

Instructions: The number given in the input is 57. The number 57 can be expressed as the product of 19 and 3 (i.e. 19*3). Since both factors are distinct primes of the form 4t 3.

19=4*4 3, the value of t in this example is 4.

3=4*0 3, the value of t is 0.

Therefore, the number 57 is a blum integer.

INPUT : N=49
OUTPUT : No

Instructions: The number given is 49, which can be expressed as 7*7. Because 7 is a prime number, but for a number it should be the product of two different prime numbers. Therefore, 49 is not a fuzzy integer.

INPUT : N=35
OUTPUT : No

Explanation: The number 35 can be expressed as the product of 7 and 5 (i.e. 7*5). Both numbers are different primes, 7 is of the form 4t 3, but 5 cannot be represented as 4t 3 for any integer value of t. Therefore, 35 is not an ambiguous integer.

Let's understand the algorithm to check if the number is a blum integer.

algorithm

To check if the number is a blum integer, we can simply find all the prime numbers before the number and then check if the product of two different prime numbers of the form 4t 3 can form the given number.

We will use the concept of Sieve of Eratosthenes to find all prime numbers up to a given number N. The Sieve of Eratosthenes is the most efficient way to find the number of prime numbers preceding any given number N.

• In this method, we will create a boolean array of size N 1, where N is the given number. If the number is a prime number whose index value is equal to this number, we will store true, otherwise we will store false in the array.

• To update the index value false corresponding to the non-prime number until N, we will iterate from i=2 to i<=sqrt(N) in the for loop, because any number less than or equal to N, if it is not A prime number must have a factor in the range [2, sqrt(N)]. <=sqrt(N)，因为任何小于或等于 N 的数字，如果它不是质数，则必须有一个位于 [2, sqrt(N)] 范围内的因子。

• If the value of arr[i] corresponding to i is true, we will iterate from p=i*i in the nested loop until p<=N, and update false at all next multiples of p . If it is false at the corresponding value of i, we iterate to the next value of i. <=N，并在 p 的所有下一个倍数处更新 false。如果在 i 的相应值处为 false，我们将迭代 i 的下一个值。

Using the sieve of Eratosthenes, we can get all prime numbers from 1 to N. Now, iterating in the for loop in the array, we will check if there is any prime number which is a factor of the given number N and is of the form 4t 3 and the quotient of a prime number divided by N is also a different prime number of the form 4t 3 . The given number N will be a blum integer if all the above conditions are met, otherwise it is not.

We will use this algorithm in our approach in order to solve the problem efficiently.

method

Given below are the steps to implement the algorithm in our approach to check if N is a blum integer -

• We will create a function to check if the number is a blum integer.

• In the function, using the concept of the Sieve of Eratosthenes, we store true for all prime numbers in a boolean array of size N 1 up to N at the corresponding index.

• Iterate from i=2 to i<=N in a for loop to check if any prime number of the form 4t 3 is a factor of the given number. <=N，以检查 4t+3 形式的任何素数是否是给定数字的因子。

• If we find any prime number that is a factor of N in the form 4t 3, we will store the quotient of N divided by that prime number.

• We will return true if the quotient is also prime and of the form 4t 3, false otherwise.

• If the function returns true, the number is a blum integer.

Example

C code for this method -

// 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;
}

Output

469 is a blum integer.

Time complexity: O(N*log(log(N)), because it is the time complexity of the sieve of Eratosthenes.

Space complexity: O(N), because we use an array of size N 1 to store the prime numbers.

in conclusion

The concept of blum integers is discussed in the article. In this paper, we propose an efficient way to check whether a number is a blum integer using the concept of the Sieve of Eratosthenes in C.

I hope that after reading this article, you have clearly understood the concept of blum integer and understood the method of checking whether the number is a blum integer.

The above is the detailed content of bloom integer. For more information, please follow other related articles on the PHP Chinese website!