nombre entier de floraison

L'énoncé du problème consiste à vérifier un numéro donné qui sera saisi en tant que saisie utilisateur s'il s'agit d'un numéro Blum.

A Blum entier est un nombre semi-premier dont les facteurs premiers a et b sont de la forme 4t+3, où t est un entier positif. Un nombre semi-premier est un nombre qui est le produit d’exactement deux nombres premiers, ou un nombre naturel qui a exactement deux facteurs premiers. Pour les semi-primes, les facteurs peuvent être égaux.

Si un nombre N est un entier blum, il ne doit avoir que deux facteurs, disons N=a*b, au lieu de 1 et le nombre lui-même et les deux facteurs, a et b doivent être des nombres premiers différents de la forme 4t+3 ( pour tout entier positif t).

Les premiers entiers de Blum sont 21, 33, 57, 69, 77, 93, 129, 133, 141...

Aucun nombre naturel pair ne peut être un entier flou car le produit de deux facteurs non premiers (de la forme 4t+3 (c'est-à-dire un nombre impair)) sera toujours un nombre impair supérieur à 20.

Dans ce problème, on nous donnera un nombre N et nous devons vérifier si le nombre est un entier blum.

Exemple

INPUT : N=57
OUTPUT : yes

Instructions : Le nombre indiqué dans l'entrée est 57. Le nombre 57 peut être exprimé comme le produit de 19 et 3 (c'est-à-dire 19*3). Puisque les deux facteurs sont des nombres premiers distincts de la forme 4t+3.

19=4*4+3, la valeur de t dans cet exemple est 4.

3=4*0+3, la valeur de t est 0.

Ainsi, le nombre 57 est un entier blum.

INPUT : N=49
OUTPUT : No

Explication : Le nombre donné est 49, qui peut être exprimé par 7*7. Parce que 7 est un nombre premier, mais pour un nombre, il doit être le produit de deux nombres premiers différents. Par conséquent, 49 n’est pas un entier flou.

INPUT : N=35
OUTPUT : No

Explication : Le nombre 35 peut être exprimé comme le produit de 7 et 5 (soit 7*5). Les deux nombres sont des nombres premiers différents, 7 est de la forme 4t+3, mais 5 ne peut pas être représenté comme 4t+3 pour une valeur entière de t. 35 n’est donc pas un entier ambigu.

Comprenons l'algorithme pour vérifier si le nombre est un entier blum.

Algorithme

Pour vérifier si le nombre est un entier blum, nous pouvons simplement trouver tous les nombres premiers avant le nombre puis vérifier si le produit de deux nombres premiers différents sous la forme 4t+3 peut former le nombre donné.

Nous utiliserons le concept de Sieve d'Eratosthène pour trouver tous les nombres premiers jusqu'à un nombre N donné. Le tamis d'Ératosthène est le moyen le plus efficace de trouver le nombre de nombres premiers précédant un nombre N donné.

• Dans cette méthode, nous allons créer un tableau booléen de taille N+1, où N est le nombre donné. Si le nombre est un nombre premier dont la valeur d'index est égale à ce nombre, nous stockerons vrai, sinon nous stockerons faux dans le tableau.

• Pour mettre à jour la valeur d'index false correspondant au nombre non premier jusqu'à N, nous allons itérer de i=2 à i<=sqrt(N) dans la boucle for, car tout nombre inférieur ou égal à N, s'il n'est pas un nombre premier, il doit y avoir un facteur dans la plage [2, sqrt(N)]. <=sqrt(N)，因为任何小于或等于 N 的数字，如果它不是质数，则必须有一个位于 [2, sqrt(N)] 范围内的因子。

• Si la valeur de arr[i] correspondant à i est vraie, nous allons parcourir de p=i*i jusqu'à p<=N dans une boucle imbriquée et mettre à jour false à tous les multiples suivants de p. Si c'est faux à la valeur correspondante de i, nous passons à la valeur suivante de i. <=N，并在 p 的所有下一个倍数处更新 false。如果在 i 的相应值处为 false，我们将迭代 i 的下一个值。

En utilisant le tamis d'Ératosthène, nous pouvons obtenir tous les nombres premiers de 1 à N. Maintenant, en itérant dans la boucle for du tableau, nous allons vérifier s'il existe un nombre premier qui est un facteur du nombre donné N et est de la forme 4t+3 et le quotient d'un nombre premier divisé par N est également de la forme 4t+3 Différents nombres premiers. Le nombre N donné sera un entier blum si toutes les conditions ci-dessus sont remplies, sinon il ne l'est pas.

Nous utiliserons cet algorithme dans notre approche afin de résoudre le problème efficacement.

Méthode

Vous trouverez ci-dessous les étapes pour implémenter l'algorithme dans notre approche pour vérifier si N est un entier blum -

• Nous allons créer une fonction pour vérifier si le nombre est un entier blum.

• Dans la fonction, en utilisant le concept de Tamis d'Eratosthène, nous stockons vrai pour tous les nombres premiers dans un tableau booléen de taille N+1 jusqu'à N à l'index correspondant.

• Parcourez de i=2 à i<=N dans une boucle for pour vérifier si un nombre premier de la forme 4t+3 est un facteur du nombre donné. <=N，以检查 4t+3 形式的任何素数是否是给定数字的因子。

• Si nous trouvons un nombre premier qui est un facteur de N sous la forme 4t+3, nous stockerons le quotient de N divisé par ce nombre premier.

• Nous retournerons vrai si le quotient est également premier et de la forme 4t+3, faux sinon.

• Si la fonction renvoie vrai, le nombre est un entier blum.

Exemple

Code C++ pour cette méthode -

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

Sortie

469 is a blum integer.

Complexité temporelle : O(N*log(log(N)), car c'est la complexité temporelle du tamis d'Eratosthène.

Complexité spatiale : O(N) car nous utilisons un tableau de taille N+1 pour stocker les nombres premiers.

Conclusion

Le concept d'entiers blum est abordé dans l'article. Dans cet article, nous proposons une manière efficace de vérifier si un nombre est un entier blum en utilisant le concept du Tamis d'Eratosthène en C++.

J'espère qu'après avoir lu cet article, vous avez clairement compris le concept d'entier blum et appris la méthode pour vérifier si le nombre est un entier blum.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!