Schädliche Zahlen

Eine Zahl gilt als schädlich, wenn sie eine positive ganze Zahl ist und die festgelegte Anzahl von Ziffern in ihrer Binärentwicklung eine Primzahl ist. Die erste schädliche Zahl ist 3, weil 3 = (11)₂. Es ist ersichtlich, dass die binäre Darstellung von 3 eine festgelegte Anzahl von Ziffern von 2 hat, was eine Primzahl ist.

Die zehn schädlichsten Zahlen sind 3, 5, 6, 7, 9, 10, 11, 12, 13, 14. Interessanterweise können Zweierpotenzen niemals schädliche Zahlen sein, da bei ihnen immer nur 1 Bit gesetzt ist. 1 ist keine Primzahl. Andererseits sind alle Zahlen, die als 2ⁿ + 1 ausgedrückt werden können, wobei n eine beliebige natürliche Zahl ist, immer schlechte Zahlen, da sie zwei gesetzte Bits haben und wir wissen, dass 2 eine Primzahl ist.

Unter Berücksichtigung der Eigenschaften dieser schädlichen Zahlen wird im folgenden Artikel eine Möglichkeit beschrieben, zu überprüfen, ob eine Zahl schädlich ist.

Problemstellung

Mit dieser Frage soll überprüft werden, ob die gegebene Zahl n eine schädliche Zahl ist, d. h. eine positive Zahl mit einer Primzahl gesetzter Bits in ihrer Binärentwicklung.

Beispiel

Input: 37

Output: Pernicious

Die Übersetzung von

Erklärung

lautet:

Erklärung

37 = binäre Darstellung von 100101.

Anzahl der Ziffern einstellen = 3

Da 3 eine Primzahl ist, ist 37 eine schlechte Zahl.

Input: 22

Output: Pernicious

Die Übersetzung von

Erklärung

lautet:

Erklärung

22 = binäre Darstellung von 10110.

Anzahl der Ziffern = 3 einstellen.

Da 3 eine Primzahl ist, ist 22 eine Teufelszahl.

Input: 71

Output: Not Pernicious

Die Übersetzung von

Erklärung

lautet:

Erklärung

Die binäre Darstellung von 71 ist 1000111.

Anzahl der Ziffern = 4 einstellen.

Da 4 keine Primzahl ist, ist 71 auch keine schlechte Zahl.

Input: 64

Output: Not Pernicious

Die Übersetzung von

Erklärung

lautet:

Erklärung

Die binäre Darstellung von 64 ist 1000000.

Stellen Sie die Anzahl der Ziffern = 1 ein.

Da 64 = 2⁶ d. h. es ist eine Potenz von 2, hat es 1 gesetztes Bit. Da 1 keine Primzahl ist, ist 64 keine Teufelszahl.

Lösung

Wir müssen wissen, ob die festgelegte Anzahl von Ziffern eine Primzahl ist, um festzustellen, ob eine Zahl böswillig ist. Die Hauptaufgabe besteht darin, die festgelegte Anzahl von Stellen in der Binärentwicklung dieser Zahl zu berechnen. Die folgende Methode kann verwendet werden, um eine festgelegte Anzahl von Ziffern zu berechnen und dann zu bestimmen, ob das Ergebnis eine Primzahl ist.

Die Methode umfasst die folgenden Schritte -

• Iterieren Sie alle Bits einer Zahl mithilfe von Schleifen- und Rechtsverschiebungsoperatoren.

• Wenn der Bitwert 1 ist, wird der Zählerstand des gesetzten Bits um 1 erhöht.

• Überprüfen Sie, ob der Endwert der Zählung eine Primzahl ist.

• Antworten anzeigen.

Algorithmus

Funktion is_prime()

• wenn (n

Rückgabefehler

• für (i von 2 bis √a)

If (a%i==0)

Rückgabefehler

• return true

Funktion count_set_bits()

• Zähler initialisieren = 0

• wenn (n > 0)

• if ((n & 1) > 0)

• Zähler = Zähler + 1

• n = n >> 1

• Retourenzähler

Funktion is_pernious()

• Zähler initialisieren

• Counter = count_set_bits(n)

• if (is_prime(counter) == true)

true zurückgeben

• Andere

Rückgabefehler

Funktion main()

• N initialisieren

• if (is_pernious())

cout

• Andere

cout

• Ausdruck

Beispiel: C++-Programm

Das Programm verwendet die Funktion

is_pernicious()

, um festzustellen, ob eine Zahl schädlich ist. Es analysiert die niedrigstwertigen Bits in jeder Iteration der Schleife, indem es den Wert am Ende jeder Iteration in der Funktion

count_set_bits()

um n nach rechts verschiebt. Dann ruft es die Funktion

is_prime()

auf, um zu erfassen, ob die festgelegte Anzahl von Ziffern eine Primzahl ist.

#include <iostream>
using namespace std;
// this function counts the number of set bits by analyzing the rightmost bit using a while loop till n > 0.
// it performs logical & operation between 1 and n to determine if the rightmost bit is set or not.
// if it is set, count is incremented by 1
// right shift the value of n to make the bit left of the rightmost bit, the new rightmost bit.
int count_set_bits(int n){
   int count = 0;
   while (n > 0){
   
      // if the rightmost bit is 1: increment count
      if ((n & 1) > 0){
         count++;
      }
      
      // right shift the value of n to examine the next least significant bit
      n = n >> 1;
   }
   return count;
}

// this function determines if count of set bits in the given number is prime
bool is_prime(int count){
   if (count < 2)
   return false;
   for (int i = 2; i * i < count; i++){
      if (count % i == 0)
      return false;
   }
   return true;
}

// this functions states if count of set bits is prime -> pernicious
bool is_pernicious(int n){
   int count;
   count = count_set_bits(n);
   
   // if count is prime return true
   if (is_prime(count)){
      return true;
   }
   return false;
}

// main function
int main(){
   int n = 11;
   if (is_pernicious(n)){
      cout << n <<" is Pernicious Number";
   }
   else{
      cout << n << " is Non-Pernicious Number";
   }
   return 0;
}

Ausgabe

11 is Pernicious Number

Raum-Zeit-Analyse

Zeitliche Komplexität: O(log(n) + sqrt(count)). In der Funktion count_set_bits() wird die Schleife log(n) Mal ausgeführt, während wir die Zahl Stück für Stück analysieren. Die Funktion is_prime() benötigt O(sqrt(count)) Zeit, um zu prüfen, ob count eine Primzahl ist. Beide Funktionen werden während der Ausführung einmal aufgerufen.

Raumkomplexität: O(1), da bei der Implementierung kein Hilfsraum verwendet wird. Unabhängig von der Größe der eingegebenen Zahl verwendet der Algorithmus immer eine konstante Menge an Speicherplatz.

Fazit

Schlechte Zahlen sind ein interessantes mathematisches Konzept und können mit der oben beschriebenen Methode einfach und effektiv identifiziert werden. In diesem Artikel werden auch der zu verwendende Algorithmus, die C++-Programmlösung und die Zeit- und Raumkomplexitätsanalyse beschrieben.

Das obige ist der detaillierte Inhalt vonSchädliche Zahlen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!