In diesem Tutorial lernen Sie, wie Sie ein Python-Programm schreiben, um zu überprüfen, ob eine Zahl eine Primzahl ist oder nicht.
Wenn Sie schon einmal mit Codierungstests begonnen haben, sind Sie auf die mathematische Frage zum Test auf Primzahl gestoßen oder um zu überprüfen, ob eine Zahl eine Primzahl ist. Und in den nächsten Minuten lernen Sie, die optimale Lösung für diese Frage zu finden.
In diesem Tutorial werden Sie:
- die Grundlagen der Primzahlen wiederholen,
- Schreiben Sie Python-Code, um zu prüfen, ob eine Zahl eine Primzahl ist, und
- Optimieren Sie es weiter, um einen O(√n)-Laufzeitalgorithmus zu erhalten.
Lassen Sie uns für all dies und mehr loslegen.
Inhaltsverzeichnis
Was ist eine Primzahl?
Beginnen wir damit, die Grundlagen der Primzahlen zu wiederholen.
In der Zahlentheorie soll eine natürliche Zahl n sein prim wenn es genau zwei Faktoren hat: 1 und die Zahl selbst (n). Erinnere dich an deine Schulmathematik: Eine Zahl i heißt Teiler der Zahl n, wenn n durch i teilbar ist. ✅
Die folgende Tabelle listet einige Zahlen auf, alle ihre Faktoren und ob sie Primzahlen sind.
nFactorsIst Prime?11Nein21, 2Ja31, 3Ja41, 2, 4Nein71, 7Ja151, 3, 5, 15Nein
Aus der obigen Tabelle können wir Folgendes aufschreiben:
- 2 ist die kleinste Primzahl.
- 1 ist ein Faktor jeder Zahl.
- Jede Zahl n ist ein Faktor für sich.
Also sind 1 und n triviale Faktoren für jede Zahl n. Und eine Primzahl sollte keine anderen Faktoren als diese beiden haben.
Das bedeutet, wenn Sie von 2 zu n – 1 gehen, sollten Sie keinen nicht-trivialen Faktor finden können, der n ohne Rest teilt.
O(n) Algorithmus zum Prüfen, ob eine Zahl in Python eine Primzahl ist
Lassen Sie uns in diesem Abschnitt den obigen Ansatz in einer Python-Funktion formalisieren.
Sie können alle Zahlen von 2 bis n – 1 mit dem range()-Objekt in Python durchlaufen.
In Python gibt range(start, stop, step) ein Bereichsobjekt zurück. Sie können dann über das Range-Objekt iterieren, um eine Sequenz vom Start bis zum Stopp -1 in Schrittschritten zu erhalten.
Da wir die Menge der ganzen Zahlen von 2 bis n-1 benötigen, können wir range(2, n) angeben und in Verbindung mit der for-Schleife verwenden.
Folgendes möchten wir tun:
- Wenn Sie eine Zahl finden, die n ohne Rest teilbar ist, können Sie sofort schlussfolgern, dass die Zahl keine Primzahl ist.
- Wenn Sie den gesamten Zahlenbereich von 2 bis hinauf zu n – 1 durchlaufen haben, ohne eine Zahl zu finden, die n gleichmäßig teilt, dann ist die Zahl eine Primzahl.
Python-Funktion zum Prüfen auf Primzahl
Mit dem Obigen können wir fortfahren und die Funktion is_prime() wie folgt definieren.
def is_prime(n):
for i in range(2,n):
if (n%i) == 0:
return False
return True
Analysieren wir nun die obige Funktionsdefinition.
- Die obige Funktion is_prime() nimmt als Argument eine positive Ganzzahl n entgegen.
- Wenn Sie einen Faktor im angegebenen Bereich von (2, n-1) finden, gibt die Funktion False zurück, da die Zahl keine Primzahl ist.
- Und es gibt True zurück, wenn Sie die gesamte Schleife durchlaufen, ohne einen Faktor zu finden.
Als Nächstes rufen wir die Funktion mit Argumenten auf und überprüfen, ob die Ausgabe korrekt ist.
is_prime(2) # True is_prime(8) # False is_prime(9) # False is_prime(11) # True
In der obigen Ausgabe sehen Sie, dass 2 und 11 Primzahlen sind (die Funktion gibt True zurück). Und 8 und 9 sind keine Primzahlen (die Funktion gibt False zurück).
So optimieren Sie die Python-Funktion is_prime()
Hier können wir eine kleine Optimierung vornehmen. Beachten Sie die Liste der Faktoren in der folgenden Tabelle.
AnzahlFaktoren61, 2, 3, 6101, 2, 5, 10181, 2, 3, 6, 9, 18
Nun, wir können sehen, dass der einzige Faktor von n, der größer als n/2 ist, n selbst ist.
Das bedeutet also, dass Sie nicht bis n – 1 schleifen müssen. Sie können die Schleife stattdessen nur bis n/2 laufen lassen.
Wenn Sie bis n/2 keinen nicht-trivialen Faktor finden, können Sie auch keinen über n/2 hinaus finden.
Ändern wir nun die Funktion is_prime(), um nach Faktoren im Bereich (2, n/2) zu suchen.
def is_prime(n):
for i in range(2,int(n/2)):
if (n%i) == 0:
return False
return True
Lassen Sie uns fortfahren und die Ausgabe durch ein paar Funktionsaufrufe überprüfen.
is_prime(9) # False is_prime(11) # True
Auch wenn es den Anschein hat, als hätten wir optimiert, ist dieser Algorithmus in Bezug auf die Laufzeitkomplexität nicht effizienter als der vorherige. Tatsächlich haben beide eine Laufzeitkomplexität von O(n): proportional zum Wert von n oder linear in n.
Können wir es besser machen? Ja wir können!
▶️ Fahren Sie mit dem nächsten Abschnitt fort, um zu bestimmen, wie Sie die Zeitkomplexität für Primzahltests verbessern können.
O(√n) Algorithmus zur Prüfung auf Primzahl in Python
Es kommt vor, dass die Faktoren einer Zahl paarweise auftreten.
Wenn a ein Faktor der Zahl n ist, dann gibt es auch einen Faktor b, so dass axb = n oder einfach ab = n.
Lassen Sie uns dies anhand eines Beispiels überprüfen.
Die folgende Tabelle zeigt die paarweise auftretenden Faktoren der Zahl 18. Sie können dasselbe für ein paar weitere Nummern überprüfen, wenn Sie möchten.
Beachten Sie auch, dass √18 ungefähr 4,24 ist.
Und in den paarweise auftretenden Faktoren (a, b) können Sie sehen, dass wenn a kleiner als 4,24 ist, dann b größer als 4,24 ist – in diesem Beispiel (2, 18) und (3, 6).
Faktoren von 18 in Paaren
Die folgende Abbildung zeigt die Faktoren von 18, aufgetragen auf dem Zahlenstrahl.
Wenn die Zahl n zufällig ein perfektes Quadrat ist, hast du a = b = √n als einen der Faktoren.
▶️ Schau dir die Faktoren von 36 in der Tabelle unten an. Da 36 ein perfektes Quadrat ist, ist a = b = 6 einer der Faktoren. Für alle anderen Faktorpaare (a, b) gilt a < 6 und b > 6.
Faktoren von 36 in Paaren
Zusammenfassend haben wir folgendes:
- Jede Zahl n kann als n = axb geschrieben werden
- Wenn n ein perfektes Quadrat ist, dann ist a = b = √n.
- Und wenn a < b, dann a < √n und b > √n.
- Sonst, wenn a > b, dann a > √n und b < √n.
Anstatt also alle ganzen Zahlen bis zu n/2 zu durchlaufen, können Sie sich dafür entscheiden, bis zu √n zu laufen. Und das ist viel effizienter als unser bisheriger Ansatz.
So ändern Sie is_prime() in den O(√n)-Algorithmus
Lassen Sie uns mit der Optimierung der Funktion fortfahren, um in Python nach Primzahlen zu suchen.
import math
def is_prime(n):
for i in range(2,int(math.sqrt(n))+1):
if (n%i) == 0:
return False
return True
Analysieren wir nun die obige Funktionsdefinition:
- Um die Quadratwurzel einer Zahl zu berechnen, importieren wir das eingebaute Mathematikmodul von Python und verwenden die Funktion math.sqrt().
- Da n möglicherweise kein perfektes Quadrat ist, müssen wir es in eine ganze Zahl umwandeln. Verwenden Sie int(var), um var in ein int umzuwandeln.
- Um sicherzustellen, dass wir tatsächlich bis zu √n prüfen, fügen wir ein Plus eins hinzu, da die Funktion range() standardmäßig den Endpunkt des Bereichs ausschließt.
Die folgende Codezelle überprüft, ob unsere Funktion is_prime() korrekt funktioniert.
is_prime(8) # False is_prime(15) # False is_prime(23) # True
Lassen Sie uns im nächsten Abschnitt ein paar einfache Diagramme erstellen, um O(n) und O(√n) visuell zu verstehen.
O(n) und O(√n) visuell vergleichen
▶️ Führen Sie das folgende Code-Snippet in einer Jupyter-Notebook-Umgebung Ihrer Wahl aus.
import numpy as np
import seaborn as sns
import pandas as pd
n = 20
x = np.arange(n)
y1 = np.sqrt(x)
y2 = x
df = pd.DataFrame({"O(√n)":y1,"O(n)":y2})
sns.set_theme()
sns.lineplot(data = df)
Das obige Snippet zeigt, wie Sie die Kurven für n und √n für einen Wertebereich zeichnen können.
- Wir verwenden die Funktion NumPy arange(), um ein Array von Zahlen zu erstellen.
- Und dann sammeln wir die Werte von n und √n bis einschließlich 20 in a Pandas DataFrame.
- Als nächstes plotten wir mit Liniendiagramm von Seaborn () Funktion.
Aus dem Diagramm unten sehen wir, dass √n deutlich kleiner als n ist.
Lassen Sie uns nun den Bereich auf bis zu 2000 erhöhen und die gleichen Schritte wie oben wiederholen.
import numpy as np
import seaborn as sns
import pandas as pd
n = 2000
x = np.arange(n)
y1 = np.sqrt(x)
y2 = x
df = pd.DataFrame({"O(√n)":y1,"O(n)":y2})
sns.set_theme()
sns.lineplot(data = df)
Aus dem obigen Diagramm können Sie schließen, dass der O(√n)-Algorithmus erheblich schneller ist, wenn Sie testen, ob eine große Zahl eine Primzahl ist.
Hier ist ein kurzes Beispiel: 2377 ist eine Primzahl – bestätige das!😀
Während der O(n)-Ansatz eine Größenordnung von 2000 Schritten benötigt, kann der O(√n)-Algorithmus helfen, die Antwort in nur 49 Schritten zu finden.✅
Fazit
⏳ Und es ist Zeit für eine kurze Zusammenfassung.
- Um zu überprüfen, ob eine Zahl eine Primzahl ist, besteht der naive Ansatz darin, alle Zahlen im Bereich (2, n-1) zu durchlaufen. Wenn Sie keinen Faktor finden, der n teilt, dann ist n eine Primzahl.
- Da der einzige Faktor von n größer als n/2 n selbst ist, können Sie sich dafür entscheiden, nur bis n/2 zu laufen.
- Beide der obigen Ansätze haben eine Zeitkomplexität von O(n).
- Da Faktoren einer Zahl paarweise vorkommen, kann man nur bis √n laufen. Dieser Algorithmus ist viel schneller als O(n). Und der Gewinn ist beträchtlich, wenn man überprüft, ob eine große Zahl eine Primzahl ist oder nicht.
Ich hoffe, Sie verstehen, wie man in Python prüft, ob eine Zahl eine Primzahl ist. Als nächsten Schritt können Sie sich unser Tutorial zu Python-Programmen zu Zeichenfolgenoperationen ansehen – in dem Sie lernen, zu überprüfen, ob Zeichenfolgen Palindrome, Anagramme und mehr sind.
Wir sehen uns alle in einem anderen Tutorial. Bis dahin viel Spaß beim Programmieren!👩🏽💻