Heim >Backend-Entwicklung >C++ >Berechnen Sie die Anzahl der Primzahlen, nachdem Sie die gegebene Binärzahl in eine Basis zwischen L und R umgewandelt haben
Der Titel „Zählung der Primzahlen nach der Umwandlung einer gegebenen Binärzahl zwischen L und R“ bezieht sich auf ein mathematisches Problem, bei dem es darum geht, eine Binärzahl in eine Basis zwischen L und R umzuwandeln und dann die Zahlen zwischen L und R zu zählen Die Anzahl der Primzahlen. Konvertieren. In der Mathematik ist eine Primzahl eine ganze Zahl größer als 1, die nur durch 1 und sich selbst teilbar ist.
Um eine Binärzahl in eine Zahl mit einer anderen Basis umzuwandeln, müssen Sie die Zahl in einem anderen Zahlensystem schreiben. Die Basis eines Zahlensystems ist die Anzahl eindeutiger Zahlen, und die Konvertierung erfolgt durch Finden einer äquivalenten Darstellung dieser Zahl in der neuen Basis. Die Berechnung von Primzahlen nach der Transformation ist ein schwieriges Problem der Zahlentheorie, das in der Kryptographie, Informatik und anderen Bereichen Anwendung findet. Um dieses Problem zu lösen, müssen Sie viel über Zahlentheorie, Primzahlen und Zahlensysteme wissen.
Eine Zahl heißt nur dann Primzahl, wenn sie durch 1 und die Zahl selbst teilbar ist. Zum Beispiel ist die Zahl 5 eine Primzahl, weil sie nur durch die Zahlen 1 und 5 teilbar ist, aber 6 ist keine Primzahl, weil sie auch durch 2 und 3 teilbar ist.
Bei der Anzahl der Primzahlen geht es einfach darum, wie viele Primzahlen es in einer gegebenen Zahlenmenge gibt. Nehmen Sie zum Beispiel eine Zahlenmenge {1,2,3,4,5,6,7,8,9}. In dieser Zahlenmenge beträgt die Anzahl der Primzahlen 4 und sie sind 2, 3, 5 , und 7. Darüber hinaus ist 1 keine Primzahl, da ihr einziger positiver Faktor 1 selbst ist.
Es gibt zwei Hauptmethoden zur Berechnung des Primzahlproblems, wie unten gezeigt −
Gewalttätige Methode
Primfaktorisierung
Schritt 1 – Geben Sie die Binärzahl und den Bereich für Basis L und R ein.
Schritt 2 – Iterieren Sie über jede Basis zwischen L und R (einschließlich).
Schritt 3 – Konvertieren Sie die Binärzahl in die aktuelle Basis.
Schritt 4 − Prüfen Sie, ob die umgewandelte Zahl eine Primzahl ist.
Schritt 5 – Wenn die umgewandelte Zahl eine Primzahl ist, erhöhen Sie die Primzahlanzahl um 1.
Schritt 6 – Wiederholen Sie die Schritte 3–5 für alle Basen im Bereich L bis R.
Schritt 7 − Geben Sie die Gesamtzahl der erhaltenen Primzahlen zurück.
Unten ist der Pseudocode des Algorithmus angegeben -
input: binary number b, range of bases L and R output: count of prime numbers in the given range Number_of_prime = 0 for base = L to R convert b to base if number_is_prime(converted_number) Number_of_prime ++ return Number_of_prime
number_is_prime() ist eine Methode, die eine Zahl als Eingabe akzeptiert und einen booleschen Wert zurückgibt, der angibt, ob die Zahl eine Primzahl ist.
Brute-Force-Ansatz beinhaltet die Konvertierung von Binärzahlen in jede Basis von L bis R und das Zählen der Anzahl der Primzahlen bei jeder Konvertierung. Bei größeren Zahlen müssen alle möglichen Variationen überprüft werden, was zeitaufwändig sein kann.
Der folgende Code enthält drei Funktionen. Die erste Funktion ist „isPrime“, die 1 zurückgibt, wenn die Eingabezahl eine Primzahl ist, andernfalls 0. Die zweite Funktion „binaryToDecimal“ wandelt eine Binärzahl in eine Dezimalzahl um. Die dritte Funktion „countPrimes“ zählt die Anzahl der Primzahlen, die durch die Umwandlung von Binärzahlen zwischen den Eingabebereichen in Dezimalzahlen erhalten werden. Schließlich nimmt die Hauptfunktion eine Binärzahl und einen Zahlenbereich auf, ruft die Funktion „countPrimes“ auf und gibt die Anzahl der Primzahlen aus.
Die chinesische Übersetzung vonDieser Code bietet vordefinierte Werte für Binärzahlen und die Bereiche L und R. In diesem Beispiel habe ich die Binärzahl 1010 und den Bereich 5 bis 20 verwendet. Sie können diese Werte in der Hauptfunktion nach Bedarf ändern.
#include <stdio.h> #include <stdlib.h> #include <math.h> // Function to check if a number is prime or not int isPrime(int n) { int i; for(i = 2; i <= sqrt(n); i++) { if(n%i == 0) { return 0; } } return 1; } // Function to convert binary to decimal int binaryToDecimal(int n) { int decimal = 0, i = 0, remainder; while(n != 0) { remainder = n % 10; n /= 10; decimal += remainder * pow(2, i); ++i; } return decimal; } // Function to count primes in a given range int countPrimes(int L, int R) { int count = 0, i; for(i = L; i <= R; i++) { int decimal = binaryToDecimal(i); if(isPrime(decimal)) { count++; } } return count; } // Main function int main() { int binary = 1010; // Example binary number int L = 5; // Example range lower limit int R = 20; // Example range upper limit // Count primes and print result int count = countPrimes(L, R); printf("Number of primes after converting %d to base between %d and %d is: %d\n", binary, L, R, count); return 0; }
Number of primes after converting 1010 to base between 5 and 20 is: 7
Bei der Primfaktorisierung geht es darum, die Primfaktoren einer transformierten Zahl zu finden und zu prüfen, ob sie im Primzahlbereich liegen. Für kleinere Zahlen kann es eine effiziente Methode sein, für größere Zahlen kann es jedoch rechenintensiv sein.
Der folgende Code definiert zwei Funktionen, isPrime() und countPrimes(), die prüfen, ob eine bestimmte Zahl eine Primzahl ist, oder die Anzahl der Primzahlen vor einer bestimmten Zahl zählen. Die Hauptfunktion akzeptiert eine Binärzahl und eine vom Benutzer eingegebene Basiszahl, wandelt die Binärzahl in eine Dezimalzahl um und wandelt sie dann innerhalb der angegebenen Grenzen in eine andere Basiszahl um. Bei jeder Umrechnung sucht das Programm nach Primfaktoren und erhöht einen Zähler, wenn diese innerhalb der aktuellen Basisgrenzen liegen. Abschließend gibt das Programm die Anzahl der gefundenen Primzahlen aus. Der Code importiert die Standard-Eingabe-/Ausgabe-Bibliotheken und die booleschen Bibliotheken.
Die chinesische Übersetzung von#include <stdio.h> #include <stdbool.h> #include <math.h> bool isPrime(int n) { if (n <= 1) { return false; } int i; for (i = 2; i <= sqrt(n); i++) { if (n % i == 0) { return false; } } return true; } int main() { int binaryNum = 110101; // Predefined binary number input int L = 3; // Predefined lower limit of base int R = 6; // Predefined upper limit of base int decimalNum = 0, base = 1; while (binaryNum > 0) { int digit = binaryNum % 10; decimalNum += digit * base; base *= 2; binaryNum <span>/</span>= 10; } int transformedNum, factor; int primeCount = 0; for (int baseNum = L; baseNum <= R; baseNum++) { transformedNum = decimalNum; while (transformedNum > 1) { for (int i = 2; i <= transformedNum; i++) { if (transformedNum % i == 0) { factor = i; break; } } transformedNum <span>/</span>= factor; if (isPrime(factor) && factor >= baseNum) { primeCount++; } } } printf("Count of primes after converting the given binary number in base between L to R is: %d", primeCount); return 0; }
Count of primes after converting the given binary number in base between L to R is: 4
Zusammenfassend können wir die Anzahl der Primzahlen bestimmen, indem wir zunächst eine gegebene Binärzahl in eine Basis zwischen L und R umwandeln und dann die Anzahl der Primzahlen in diesem Bereich zählen.
Das obige ist der detaillierte Inhalt vonBerechnen Sie die Anzahl der Primzahlen, nachdem Sie die gegebene Binärzahl in eine Basis zwischen L und R umgewandelt haben. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!