In der Welt der Computerprogrammierung kann es eine häufige Aufgabe sein, die Anzahl der Zahlen in einem bestimmten Bereich zu ermitteln, die teilerfremd zu einer bestimmten Zahl sind. Relative Primzahlen, auch relative Primzahlen genannt, sind Zahlen, die außer 1 keinen gemeinsamen Teiler haben. In diesem Artikel werden wir untersuchen, wie wir mithilfe der C++-Sprache die Anzahl der Zahlen ermitteln können, die zwischen den gegebenen ganzen Zahlen L und R teilerfremd zu einer bestimmten Zahl P sind.
Wir werden zunächst die Syntax der Methoden skizzieren, die wir in den folgenden Codebeispielen verwenden werden –
int countCoprimes(int L, int R, int P);
Der Algorithmus, den wir zur Berechnung der Anzahl der teilerfremden Zahlen verwenden werden, lautet wie folgt: −
Initialisieren Sie die Variablenanzahl auf 0, die zum Speichern der Anzahl der teilerfremden Zahlen verwendet wird.
Iterieren Sie jede Zahl von L bis R.
Überprüfen Sie für jede Zahl, ob sie relativ teilerfremd mit P ist.
Wenn num und P teilerfremd sind, erhöhen Sie die Anzahl um 1.
Gibt den Endwert von count zurück.
Die erste Methode, die wir besprechen werden, ist die naive Methode. Um die Koprimeität mit P mithilfe des Euklidischen Algorithmus zu überprüfen, erfordert diese Methode die iterative Überprüfung jeder Zahl innerhalb eines angegebenen Bereichs.
Die chinesische Übersetzung von
#include <iostream>
int countCoprimes(int L, int R, int P) {
int count = 0;
for (int num = L; num <= R; num++) {
int a = num;
int b = P;
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
if (a == 1)
count++;
}
return count;
}
int main() {
int L = 1; // Set the starting range value
int R = 100; // Set the ending range value
int P = 7; // Set the value of P
int result = countCoprimes(L, R, P);
std::cout << "Count of numbers between " << L << " and " << R << " coprime with " << P << ": " << result << std::endl;
return 0;
}
Count of numbers between 1 and 100 coprime with 7: 86
Die countCoprimes-Funktion akzeptiert drei Parameter: L (Anfangsbereichswert), R (Endbereichswert) und P (Wert von P).
Innerhalb der countCoprimes-Funktion initialisieren wir eine Variable count auf 0, die die Anzahl der Coprimes speichert.
Die for-Schleife iteriert jede Zahl num von L bis R.
In der Schleife initialisieren wir die Variablen a und b auf num bzw. P.
Wir verwenden den euklidischen Algorithmus in einer While-Schleife, um den größten gemeinsamen Teiler (GCD) von a und b zu finden, indem wir wiederholt modulare Operationen austauschen und ausführen.
Wenn GCD (gespeichert in a) gleich 1 ist, bedeutet dies, dass num und P teilerfremd sind. In diesem Fall erhöhen wir die Zählvariable.
Wir finalisieren unseren Zählwert, indem wir alle Zahlen sorgfältig durchlaufen und ihn zurückgeben, wenn er fertig ist.
Hauptfunktionen weisen L-, R- und P-Variablen sorgfältig geeignete Werte zu.
Wir rufen dann die Funktion countCoprimes mit dem bereitgestellten Wert auf und speichern das Ergebnis in der Ergebnisvariablen.
Schließlich zeigen wir das Ergebnis an, nämlich die Anzahl der Zahlen zwischen L und R, die teilerfremd zu P sind.
Diese Strategie beinhaltet die Ausnutzung der Primfaktorzerlegung von P, um die Anzahl der teilerfremden ganzen Zahlen, die zwischen L und R liegen, genau zu berechnen.
Die chinesische Übersetzung von#include <iostream>
#include <unordered_set>
int countCoprimes(int L, int R, int P) {
std::unordered_set<int> factors;
int tempP = P;
for (int i = 2; i * i <= tempP; i++) {
while (tempP % i == 0) {
factors.insert(i);
tempP /= i;
}
}
if (tempP > 1)
factors.insert(tempP);
int count = 0;
for (int num = L; num <= R; num++) {
bool isCoprime = true;
for (int factor : factors) {
if (num % factor == 0) {
isCoprime = false;
break;
}
}
if (isCoprime)
count++;
}
return count;
}
int main() {
int L = 1; // Set the starting range value
int R = 100; // Set the ending range value
int P = 7; // Set the value of P
int result = countCoprimes(L, R, P);
std::cout << "Count of numbers between " << L << " and " << R << " coprime with " << P << ": " << result << std::endl;
return 0;
}
Count of numbers between 1 and 100 coprime with 7: 86
Die countCoprimes-Funktion akzeptiert drei Parameter: L (Anfangsbereichswert), R (Endbereichswert) und P (Wert von P).
Wir erstellen einen ungeordneten Satz von Faktoren, um die Primfaktoren von P zu speichern. Wir initialisieren eine temporäre Variable tempP auf P.
Wir iterieren von 2 bis zur Quadratwurzel von tempP. Wenn tempP durch i teilbar ist, fügen wir i zur Menge der Faktoren hinzu und dividieren tempP durch i, bis tempP nicht mehr durch i teilbar ist.
Wenn tempP nach der obigen Schleife größer als 1 ist, bedeutet dies, dass es sich selbst um eine Primzahl handelt und zum Faktor addiert werden sollte.
Wir initialisieren die Variable count auf 0, wodurch die Anzahl der teilerfremden Zahlen gespeichert wird.
Wir iterieren über jede Zahl von L bis R und prüfen, ob sie durch einen beliebigen Faktor in den eingestellten Faktoren teilbar ist. Wenn wir können, bezeichnen wir es als nicht-koprimiert.
Nach Abschluss der Iteration aller Zahlen wird die resultierende Anzahl als Endwert zurückgegeben. Die Hauptfunktion initialisiert L, R und P mit den angegebenen Werten.
Wir rufen dann die countCoprimes-Funktion mit dem bereitgestellten Wert auf und speichern das Ergebnis in der Ergebnisvariablen.
Schließlich zeigen wir das Ergebnis an, nämlich die Anzahl der Zahlen zwischen L und R, die teilerfremd zu P sind.
Die Berechnung von Koprimzahlen innerhalb eines bestimmten Bereichs L-R und die Erfüllung eines bestimmten Werts P ist eine gute Herausforderung für Programmierer – aber was ist auf Codeebene der beste Ansatz? Im Rahmen dieses Artikels befassen wir uns eingehend mit zwei C++-Anwendungsfällen, die bei der Lösung solcher Probleme echte Effizienz bieten. Erstens: Durch Iteration über alle Werte innerhalb des Zielintervalls und Verwendung des euklidischen Algorithmus wird überprüft, ob die Zahlen übereinstimmen, um teilerfremd zu sein. Darüber hinaus gibt es auch die Euler-Funktionsmethode, die eine Optimierungsstrategie verwendet. Unabhängig davon, welche Methode Sie verwenden, hängt es weitgehend von Kontextfaktoren ab, wie den von Ihnen gewählten Zahlen und den von Ihnen angegebenen Intervallen, ob Sie den größtmöglichen Nutzen daraus ziehen können. Eine fundierte Wahl zwischen den beiden möglichen Methoden kann die Sache jedoch insgesamt erheblich beschleunigen. Die Ausführungsgeschwindigkeit des Programms. Für Programmierer, die ihre technischen Fähigkeiten und kreativen Problemlösungsfähigkeiten um technisches Know-how erweitern möchten, ist die Beherrschung der Coprime-Zahlenzählung mit C++ mithilfe dieser Methoden möglicherweise genau das Richtige.
Das obige ist der detaillierte Inhalt vonÜbersetzen Sie in C++ Folgendes ins Chinesische: Zählen Sie die Anzahl der Zahlen zwischen L und R, die teilerfremd zu P sind. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
![[Web-Frontend] Node.js-Schnellstart](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
