Bloom-Ganzzahl

Die Problemstellung besteht darin, eine gegebene Zahl zu prüfen, die als Benutzereingabe eingegeben wird, ob es sich um eine Blum-Zahl handelt.

A Blum-Ganzzahl ist eine Halbprimzahl, deren Primfaktoren a und b die Form 4t+3 haben, wobei t eine positive ganze Zahl ist. Eine Halbprimzahl ist eine Zahl, die das Produkt von genau zwei Primzahlen ist, oder eine natürliche Zahl, die genau zwei Primfaktoren hat. Bei Halbprimzahlen können die Faktoren gleich sein.

Wenn eine Zahl N eine Blum-Ganzzahl ist, darf sie nur zwei Faktoren haben, sagen wir N=a*b, statt 1 und die Zahl selbst und die beiden Faktoren a und b müssen verschiedene Primzahlen der Form 4t+3 sein ( für jede positive ganze Zahl t).

Die ersten paar Blum-Ganzzahlen sind 21, 33, 57, 69, 77, 93, 129, 133, 141...

Keine gerade natürliche Zahl kann eine unscharfe ganze Zahl sein, da das Produkt zweier Nicht-Primfaktoren (der Form 4t+3 (d. h. eine ungerade Zahl)) immer eine ungerade Zahl größer als 20 ist.

In diesem Problem erhalten wir eine Zahl N und müssen prüfen, ob die Zahl eine Blum-Ganzzahl ist.

Beispiel

INPUT : N=57
OUTPUT : yes

Anleitung: Die in der Eingabe angegebene Zahl ist 57. Die Zahl 57 kann als Produkt von 19 und 3 (d. h. 19*3) ausgedrückt werden. Da beide Faktoren unterschiedliche Primzahlen der Form 4t+3 sind.

19=4*4+3, der Wert von t in diesem Beispiel ist 4.

3=4*0+3, der Wert von t ist 0.

Die Zahl 57 ist also eine Blum-Ganzzahl.

INPUT : N=49
OUTPUT : No

Erklärung: Die angegebene Zahl ist 49, was als 7*7 ausgedrückt werden kann. Denn 7 ist eine Primzahl, aber für eine Zahl sollte sie das Produkt zweier verschiedener Primzahlen sein. Daher ist 49 keine Fuzzy-Ganzzahl.

INPUT : N=35
OUTPUT : No

Erklärung: Die Zahl 35 kann als Produkt von 7 und 5 (d. h. 7*5) ausgedrückt werden. Beide Zahlen sind unterschiedliche Primzahlen, 7 hat die Form 4t+3, aber 5 kann für keinen ganzzahligen Wert von t als 4t+3 dargestellt werden. Daher ist 35 keine mehrdeutige ganze Zahl.

Lassen Sie uns den Algorithmus verstehen, mit dem überprüft wird, ob die Zahl eine Blum-Ganzzahl ist.

Algorithmus

Um zu überprüfen, ob die Zahl eine Blum-Ganzzahl ist, können wir einfach alle Primzahlen vor der Zahl finden und dann prüfen, ob das Produkt zweier verschiedener Primzahlen in der Form 4t+3 die gegebene Zahl bilden kann.

Wir werden das Konzept des Sieb des Eratosthenes verwenden, um alle Primzahlen bis zu einer bestimmten Zahl N zu finden. Das Sieb des Eratosthenes ist die effizienteste Methode, um die Anzahl der Primzahlen vor einer bestimmten Zahl N zu ermitteln.

• In dieser Methode erstellen wir ein boolesches Array der Größe N+1, wobei N die angegebene Zahl ist. Wenn es sich bei der Zahl um eine Primzahl handelt, deren Indexwert dieser Zahl entspricht, speichern wir „true“, andernfalls speichern wir „false“ im Array.

• Um den Indexwert false entsprechend der Nicht-Primzahl bis N zu aktualisieren, werden wir in der for-Schleife von i=2 bis i

• Wenn der Wert von arr[i], der i entspricht, wahr ist, iterieren wir von p=i*i bis p

Mit dem Sieb des Eratosthenes können wir alle Primzahlen von 1 bis N erhalten. Indem wir nun die for-Schleife im Array durchlaufen, prüfen wir, ob es eine Primzahl gibt, die ein Faktor der gegebenen Zahl N ist und die Form 4t+3 hat und der Quotient einer Primzahl dividiert durch N ebenfalls ist die Form 4t+3 Verschiedene Primzahlen. Die angegebene Zahl N ist eine Blum-Ganzzahl, wenn alle oben genannten Bedingungen erfüllt sind, andernfalls nicht.

Wir werden diesen Algorithmus in unserem Ansatz verwenden, um das Problem effizient zu lösen.

Methode

Im Folgenden finden Sie die Schritte zur Implementierung des Algorithmus in unserem Ansatz zur Überprüfung, ob N eine Blum-Ganzzahl ist -

• Wir erstellen eine Funktion, um zu prüfen, ob die Zahl eine Blum-Ganzzahl ist.

• In der Funktion speichern wir unter Verwendung des Konzepts von Sieve of Eratosthenes wahr für alle Primzahlen in einem booleschen Array der Größe N+1 bis N am entsprechenden Index.

• Iterieren Sie in einer for-Schleife von i=2 bis i

• Wenn wir eine Primzahl finden, die ein Faktor von N in der Form 4t+3 ist, speichern wir den Quotienten von N dividiert durch diese Primzahl.

• Wir geben true zurück, wenn der Quotient ebenfalls eine Primzahl ist und die Form 4t+3 hat, andernfalls false.

• Wenn die Funktion „true“ zurückgibt, ist die Zahl eine Blum-Ganzzahl.

Beispiel

C++-Code für diese Methode -

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

Ausgabe

469 is a blum integer.

Zeitliche Komplexität: O(N*log(log(N)), weil es die zeitliche Komplexität des Siebes des Eratosthenes ist.

Raumkomplexität: O(N), weil wir ein Array der Größe N+1 verwenden, um die Primzahlen zu speichern.

Fazit

Das Konzept der Blum-Ganzzahlen wird im Artikel besprochen. In diesem Artikel schlagen wir eine effiziente Möglichkeit vor, mithilfe des Konzepts des Siebs von Eratosthenes in C++ zu überprüfen, ob eine Zahl eine Blum-Ganzzahl ist.

Hoffentlich haben Sie nach dem Lesen dieses Artikels das Konzept der Blum-Ganzzahl klar verstanden und die Methode kennengelernt, mit der Sie überprüfen können, ob die Zahl eine Blum-Ganzzahl ist.

Das obige ist der detaillierte Inhalt vonBloom-Ganzzahl. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!