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)2. 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 2n + 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.
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.
Input: 37
Output: Pernicious
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
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 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 binäre Darstellung von 64 ist 1000000.
Stellen Sie die Anzahl der Ziffern = 1 ein.
Da 64 = 26 d. h. es ist eine Potenz von 2, hat es 1 gesetztes Bit. Da 1 keine Primzahl ist, ist 64 keine Teufelszahl.
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.
Funktion is_prime()
wenn (n < 2)< 2)
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 <<"schädliche Nummer"<<“Schädliche Zahlen字”
Andere
cout << „Unschädliche Zahl“
Ausdruck
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 Funktioncount_set_bits()
um n nach rechts verschiebt. Dann ruft es die Funktionis_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;
}
11 is Pernicious Number
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.
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!
Algorithmus zum Ersetzen von Seiten
So reparieren Sie das Win7-System, wenn es beschädigt ist und nicht gestartet werden kann
So öffnen Sie eine DMP-Datei
Wie man Go-Sprache von Grund auf lernt
Detaillierte Erläuterung der Verwendung der Oracle-Substr-Funktion
So entsperren Sie die Passwortsperre auf Ihrem Apple-Telefon, wenn Sie sie vergessen
Was ist Pr
Was bedeutet BBS?
![[Web-Frontend] Node.js-Schnellstart](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
