Überprüfen einer Primzahl in einer Python mit Rekursion

Die Überprüfung einer Zahl auf Einfachheit ist eine wichtige Aufgabe in der Programmierung, insbesondere bei der Arbeit mit Algorithmen und Aufgaben, die die Definition von Primzahlen erfordern. In Python gibt es mehrere Möglichkeiten, eine Zahl auf Einfachheit zu überprüfen, eine davon ist die Verwendung von Rekursion.

Rekursion ist eine Methode zur Lösung eines Problems, bei dem eine Funktion sich selbst aufruft. Wenn eine Zahl auf Einfachheit überprüft wird, können wir eine rekursive Funktion schreiben, die die Zahl durch alle Zahlen von 2 bis zur Wurzel dieser Zahl teilt. Wenn der Rest der Division Null ist, ist die Zahl keine Primzahl.

Es ist wichtig zu beachten, dass Rekursion möglicherweise nicht der effektivste Weg ist, um eine Zahl auf Einfachheit zu überprüfen, insbesondere für große Zahlen. Die Verwendung von Rekursion in diesem Fall ermöglicht jedoch, das Funktionsprinzip des Algorithmus deutlich zu demonstrieren und seine Logik zu verstehen.

Wie überprüfe ich eine Zahl auf Einfachheit in Python

Eine Primzahl ist eine natürliche Zahl, die größer als eine Einheit ist und nicht in andere Zahlen als eine Einheit und sich selbst unterteilt ist. Um eine Zahl auf Einfachheit zu überprüfen, können Sie einen Algorithmus verwenden, um alle Zahlen von 2 bis n-1 zu durchlaufen, wobei n die zu überprüfende Zahl ist. Wenn es mindestens eine Zahl gibt, durch die n ohne Rest geteilt wird, ist die Zahl n eine zusammengesetzte Zahl, andernfalls eine einfache Zahl.

Der rekursive Algorithmus zur Überprüfung einer Zahl auf Einfachheit muss in zwei Teile geteilt werden. Im ersten Teil wird überprüft, ob die Zahl n durch Zahlen von 2 bis zur Wurzel von n geteilt wird. Wenn eine solche Zahl gefunden wird, ist die Zahl n eine zusammengesetzte Zahl. Im zweiten Teil wird die Funktion rekursiv aufgerufen, um die Zahl für alle Zahlen von 2 bis zur Wurzel von n auf Einfachheit zu überprüfen. Wenn mindestens eine Zahl aus diesem Bereich True zurückgibt, ist die Zahl n eine zusammengesetzte Zahl, andernfalls eine einfache Zahl.

Ein Vorteil der Verwendung von Rekursion ist der kompaktere und prägnantere Code, der leichter zu verstehen und zu pflegen ist. Es sollte jedoch berücksichtigt werden, dass ein rekursiver Algorithmus eine höhere Komplexität aufweisen kann und mehr Ressourcen verbraucht als ein iterativer Algorithmus.

Beispiel für eine rekursive Funktion, um eine Zahl auf Einfachheit zu überprüfen:

def is_prime(n, i=2):if i > n**0.5:return Trueif n % i == 0:return Falsereturn is_prime(n, i+1)

Um diese Funktion zu verwenden, genügt es, sie mit dem gewünschten Argument aufzurufen:

number = 17if is_prime(number):print(f" - простое число")else:print(f" - составное число")

Wenn Sie diesen Code ausführen, erhalten Sie eine Meldung darüber, ob es sich bei der Zahl 17 um eine Primzahl oder einen zusammengesetzten Wert handelt.

Ein rekursiver Algorithmus zur Überprüfung einer Zahl auf Einfachheit ermöglicht es daher, effizient zu bestimmen, ob eine Zahl durch die Iterationsmethode einfach ist. Bevor Sie diesen Algorithmus verwenden, sollten Sie jedoch seine Komplexität bewerten und ihn nur dann verwenden, wenn der iterative Algorithmus nicht geeignet ist.

Was ist eine Primzahl

Beispiele für Primzahlen: 2, 3, 5, 7, 11, 13, 17 und so weiter. Primzahlen sind in Mathematik und Kryptographie von wesentlicher Bedeutung. Ihre Verwendung hilft dabei, Informationen zu verschlüsseln und Ihre Daten zu schützen.

Wenn Sie eine Zahl auf Einfachheit prüfen, können Sie feststellen, ob sie in kleinere Multiplikatoren zerlegt werden kann. Wenn eine Zahl keine Primzahl ist, wird sie zusammengesetzt genannt und kann in Primfaktoren zerlegt werden. Zum Beispiel ist die Zahl 12 eine zusammengesetzte Zahl, da sie in die Multiplikatoren 2 und 6 zerlegt werden kann.

Der Algorithmus zur Überprüfung einer Zahl auf Einfachheit beinhaltet das Ausschließen von Zahlen, die kleiner als 2 sind, da die minimale Primzahl 2 ist. Die Zahl wird dann auf Teilbarkeit ohne Rest durch alle Zahlen von 2 bis zur Wurzel der Zahl selbst überprüft.

Wenn der Rest, wenn er durch diese Zahlen geteilt wird, 0 ist, ist die Zahl keine Primzahl. Ansonsten ist es einfach.

Methoden zur Überprüfung auf Einfachheit

Es gibt auch eine effizientere Methode - eratosthenes Sieb. Es ermöglicht Ihnen, alle Primzahlen bis zu einer bestimmten Zahl n zu finden. Der Algorithmus ist wie folgt: es wird eine Liste von Zahlen von 2 bis n erstellt, dann gehen wir durch die Liste und durchstreichen alle Zahlen, die ein Vielfaches der aktuellen Zahl sind. Nachdem Sie die Liste durchlaufen haben, sind alle verbleibenden Zahlen einfach.

Brute-to-Teiler

Eratosthenes Sieb

- Ineffizient für große Zahlen

- Wirksam für große Zahlen

Die Auswahl der Methode zur Überprüfung auf Einfachheit hängt vom Kontext und den Anforderungen der jeweiligen Aufgabe ab. Wenn Sie nur eine Zahl überprüfen müssen, ist das Durchbrechen der Teiler eine einfache und verständliche Methode. Wenn Sie alle Primzahlen auf einen gegebenen Wert finden möchten, ist das Eratosthenisier effizienter.

Rekursiver Algorithmus zur Überprüfung einer Zahl auf Einfachheit

Eine rekursive Funktion ist eine Funktion, die sich selbst innerhalb ihrer Definition aufruft. Um eine Zahl auf Einfachheit zu überprüfen, können Sie eine rekursive Funktion verwenden, die eine gegebene Zahl in immer kleinere Zahlen teilt, beginnend mit 2 und endend mit der Wurzel der Zahl.

Ein Beispiel für einen solchen rekursiven Algorithmus könnte folgendermaßen aussehen:

def is_prime(n):if n < 2:return Falseif n == 2:return Trueif n % 2 == 0:return Falsefor i in range(3, int(n ** 0.5) + 1, 2):if n % i == 0:return Falsereturn True

In diesem Beispiel ist die Funktion is_prime überprüft die Zahl n zur Einfachheit mit Rekursion. Es beginnt mit der Überprüfung der zugrunde liegenden Fälle: wenn die Zahl n kleiner als 2 ist, ist es nicht einfach und gibt einen Wert zurück False und wenn die Zahl 2 ist, ist sie einfach und die Funktion gibt einen Wert zurück True. Die Funktion prüft dann, ob die Zahl gerade ist. Wenn die Zahl ohne Rest durch 2 geteilt wird, ist sie keine Primzahl und die Funktion gibt den Wert zurück False.

Als nächstes wird die Funktion durch Zahlen im Bereich von 3 bis zum ganzen Teil der Quadratwurzel einer Zahl durchlaufen n in Schritt 2. Sie teilt eine Zahl n für jede dieser Zahlen wird geprüft, ob sie restlos geteilt wird. Wenn eine Zahl ohne einen Rest durch eine der Zahlen geteilt wird, ist sie keine Primzahl und die Funktion gibt einen Wert zurück False.

Wenn die Schleife beendet wurde, ohne einen Teiler zu finden, bedeutet dies, dass die Zahl eine Primzahl ist und die Funktion einen Wert zurückgibt True.

Ein rekursiver Algorithmus zur Überprüfung einer Zahl auf einfache Weise ermöglicht es Ihnen, festzustellen, ob eine angegebene Zahl eine Primzahl ist oder nicht.

Implementieren eines rekursiven Algorithmus in Python

Die Implementierung eines rekursiven Algorithmus zur Überprüfung einer Zahl auf Einfachheit in Python könnte folgendermaßen aussehen:

def is_prime(n):if n n:return Trueelif n % i == 0:return Falseelse:return is_prime_recursive(n, i + 1)

In diesem Code ist die Funktion is_prime(n) überprüft, ob eine Zahl n einfachen. Wenn die Zahl kleiner oder gleich 1 ist, ist sie keine Primzahl und die Funktion gibt False zurück. Wenn die Zahl 2 ist, wird sie als Primzahl betrachtet und die Funktion gibt True zurück. In anderen Fällen ruft die Funktion eine rekursive Hilfsfunktion auf is_prime_recursive(n, i) indem ich ihr eine Zahl übergebe n und der Anfangswert i gleich 2.

Rekursive Funktion is_prime_recursive(n, i) überprüft, ob eine Zahl n einfach, beginnend mit einem Teiler i. Wenn der Teiler i übersteigt die Quadratwurzel von n, dann die Zahl n einfach und die Funktion gibt True zurück. Wenn die Zahl n restlos durch einen Teiler geteilt i, dann ist es nicht einfach und die Funktion gibt False zurück. In anderen Fällen ruft die Funktion sich selbst auf, indem sie eine Zahl übergibt n und erhöhter Teilerwert i auf 1.

Ein rekursiver Algorithmus ermöglicht es Ihnen, eine Zahl auf Einfachheit zu überprüfen, indem Sie die Aufgabe in einfachere Teilaufgaben aufteilen und die Funktion rekursiv aufrufen, um sie zu lösen.

Beispiel für die Verwendung eines rekursiven Algorithmus

Um eine Zahl mit einem rekursiven Algorithmus in Python auf Einfachheit zu überprüfen, können Sie den folgenden Code verwenden:

def is_prime(n, i=2):if n n:return Trueelse:return is_prime(n, i + 1)

Um eine Zahl auf Einfachheit zu überprüfen, wird die Funktion "is_prime" mit zwei Argumenten aufgerufen - die zu überprüfende Zahl und die Variable "i", die einen Zähler für die Zahlenteiler darstellt. Der ursprüngliche Wert der Variablen "i" ist 2, da der kleinste Teiler einer beliebigen Zahl die Zahl 2 ist.

Die Funktion "is_prime" beginnt die Prüfung mit mehreren Bedingungen: Wenn die Zahl kleiner oder gleich 1 ist, ist sie nicht primär und die Funktion gibt False zurück; Wenn die Zahl 2 ist, ist sie einfach und die Funktion gibt True zurück; wenn die Zahl restlos durch den aktuellen Teiler "i" geteilt wird, ist sie keine Primzahl und die Funktion gibt False zurück. wenn der Wert der Variablen "i" mit sich selbst multipliziert wird, ist die zu überprüfende Zahl größer, alle möglichen Teiler wurden bereits überprüft, und die Zahl ist eine Primzahl, gibt die Funktion True zurück.

Wenn keine der oben genannten Bedingungen erfüllt ist, ruft die Funktion sich selbst auf, um den nächsten Teiler "i + 1" zu überprüfen. Dies ist ein rekursiver Schritt des Algorithmus - die Funktion ruft sich selbst mit neuen Argumentwerten auf, bis ein Teiler gefunden wird oder der Wert "i * i" überschritten wird.

Beispiel für die Verwendung der Funktion "is_prime":

n = int(input("Введите число: "))if is_prime(n):print(f" является простым числом")else:print(f" не является простым числом")