Wie man in Python prüft, ob eine Zahl Primzahl ist

In diesem Tutorial lernen Sie, wie Sie ein Python-Programm schreiben, um zu prüfen, ob eine Zahl eine Primzahl ist oder nicht.

Wenn Sie schon einmal an einem Kodiertest teilgenommen haben, werden Sie die mathematische Frage nach dem Primzahltest oder nach der Prüfung, ob eine Zahl eine Primzahl ist, kennengelernt haben. In den nächsten Minuten werden Sie lernen, wie Sie die optimale Lösung für diese Frage finden.

In diesem Lernprogramm werden Sie:

die Grundlagen der Primzahlen besprechen,
python-Code schreiben, um zu prüfen, ob eine Zahl eine Primzahl ist, und
ihn weiter optimieren, um einen O(√n)-Laufzeitalgorithmus zu erhalten.

Für all das und mehr, lassen Sie uns beginnen.

Was ist eine Primzahl?

Lassen Sie uns zunächst die Grundlagen der Primzahlen betrachten.

In der Zahlentheorie wird eine natürliche Zahl n als Primzahl bezeichnet, wenn sie genau zwei Faktoren hat: 1 und die Zahl selbst(n). Erinnern Sie sich an Ihre Schulmathematik: Eine Zahl i gilt als Faktor der Zahl n, wenn i n gleichmäßig teilt. ✅

In der folgenden Tabelle finden Sie einige Zahlen, alle ihre Faktoren und ob sie Primzahlen sind.

n	Faktoren	Ist primär?
1	1	Nein
2	1, 2	Ja
3	1, 3	Ja
4	1, 2, 4	Nein
7	1, 7	Ja
15	1, 3, 5, 15	Nein

Aus der obigen Tabelle können wir Folgendes ablesen:

2 ist die kleinste Primzahl.
1 ist ein Faktor von jeder Zahl.
Jede Zahl n ist ein Faktor von sich selbst.

1 und n sind also triviale Faktoren für jede Zahl n. Und eine Primzahl sollte keine anderen Faktoren als diese beiden haben.

Das heißt, wenn Sie von 2 bis n – 1 gehen, sollten Sie keinen nicht-trivialen Faktor finden können, der n ohne Rest teilt.

O(n) Algorithmus zur Prüfung, ob eine Zahl eine Primzahl ist, in Python

In diesem Abschnitt wollen wir den obigen Ansatz in einer Python-Funktion formalisieren.

Mit dem range() -Objekt in Python können Sie eine Schleife durch alle Zahlen von 2 bis n – 1 ziehen.

In Python gibt range(start, stop, step) ein range-Objekt zurück. Sie können dann über das range-Objekt iterieren, um eine Folge von start bis stop -1 in Schritten von step zu erhalten.

Da wir die Menge der ganzen Zahlen von 2 bis n-1 benötigen, können wir range(2, n) angeben und es in Verbindung mit der for-Schleife verwenden.

So möchten wir vorgehen:

Wenn Sie eine Zahl finden, die n gleichmäßig teilt, ohne einen Rest zu haben, können Sie sofort feststellen, dass die Zahl nicht prim ist.

Wenn Sie in einer Schleife den gesamten Zahlenbereich von 2 bis n – 1 durchlaufen haben, ohne eine Zahl zu finden, die n gleichmäßig teilt, dann ist die Zahl prim.

Python-Funktion zur Prüfung auf eine Primzahl

Anhand der obigen Ausführungen können wir die Funktion is_prime() wie folgt definieren.

def is_prime(n):
  for i in range(2,n):
    if (n%i) == 0:
      false zurückgeben
  return True

Lassen Sie uns nun die obige Funktionsdefinition analysieren.

Die obige Funktion is_prime() nimmt eine positive ganze Zahl n als Argument entgegen.
Wenn Sie einen Faktor im angegebenen Bereich von (2, n-1) finden, gibt die Funktion Falsezurück , dadie Zahl nicht prim ist.
Und sie gibt True zurück, wenn Sie die gesamte Schleife durchlaufen, ohne einen Faktor zu finden.

Rufen wir nun die Funktion mit Argumenten auf und überprüfen, ob die Ausgabe korrekt ist.

is_prime(2)
# Wahr

is_prime(8)
# Falsch

is_prime(9)
# Falsch

is_prime(11)
# Wahr

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()

Wir können hier eine kleine Optimierung vornehmen. Sehen Sie sich die Liste der Faktoren in der folgenden Tabelle an.

Zahl	Faktoren
6	1, 2, 3, 6
10	1, 2, 5, 10
18	1, 2, 3, 6, 9, 18

Wir sehen also, dass der einzige Faktor von n, der größer als n/2 ist, n selbst ist.

Das bedeutet also, dass Sie die Schleife nicht bis zu n – 1 durchlaufen müssen, sondern nur bis n/2.

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 nun die Ausgabe durch ein paar Funktionsaufrufe überprüfen.

is_prime(9)
# Falsch

is_prime(11)
# Wahr

Auch wenn es den Anschein hat, dass wir optimiert haben, ist dieser Algorithmus in Bezug auf die Laufzeitkomplexität nicht effizienter als der vorherige. In der Tat haben beide eine Laufzeitkomplexität von O(n): proportional zum Wert von n oder linear in n.

Können wir es besser machen? Ja, das können wir!

▶️ Fahren Sie mit dem nächsten Abschnitt fort, um herauszufinden, wie man die Zeitkomplexität für Primzahlentests verbessern kann.

O(√n) Algorithmus zur Prüfung auf Primzahlen in Python

Es kommt vor, dass die Faktoren einer Zahl in Paaren auftreten.

Wenn a ein Faktor der Zahl n ist, dann gibt es auch einen Faktor b, so dass a x b = n, oder einfach ab = n.

Lassen Sie uns dies anhand eines Beispiels verifizieren.

Die folgende Tabelle zeigt die Faktoren der Zahl 18, die paarweise auftreten. Wenn Sie möchten, können Sie das Gleiche für ein paar weitere Zahlen überprüfen.

Beachten Sie auch, dass √18 ungefähr 4,24 ist.

Und bei den Faktoren, die in Paaren (a, b) vorkommen, können Sie sehen, dass, wenn a kleiner als 4,24 ist, b größer als 4,24 ist – in diesem Beispiel (2, 18) und (3, 6).

a	b
1	18
2	9
3	6

Faktoren von 18 in Paaren

Die folgende Abbildung zeigt die Faktoren von 18 auf der Zahlengeraden.

Wenn die Zahl n zufällig ein perfektes Quadrat ist, haben Sie a = b = √n als einen der Faktoren.

▶️ Sehen Sie sich 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 Faktorenpaare (a, b) gilt a 6.

a	b
1	36
2	18
3	12
4	9
6	6

Faktoren von 36 in Paaren

Zusammenfassend haben wir Folgendes:

Jede Zahl n kann geschrieben werden als n = a x b
Wenn n ein perfektes Quadrat ist, dann ist a = b = √n.
Und wenn a < b, dann ist a < √n und b > √n.
Andernfalls, wenn a > b, dann a > √n und b < √n.

Anstatt also alle ganzen Zahlen bis n/2 in einer Schleife zu durchlaufen, können Sie sich dafür entscheiden, bis √n zu laufen. Und das ist viel effizienter als unser vorheriger Ansatz.

Wie modifiziert man is_prime() zu einem O(√n) Algorithmus?

Lassen Sie uns nun die Funktion zur Prüfung auf Primzahlen in Python optimieren.


math importieren
def is_prime(n):
  for i in range(2,int(math.sqrt(n)) 1):
    if (n%i) == 0:
      return False
  return True

Lassen Sie uns nun die obige Funktionsdefinition analysieren:

Um die Quadratwurzel einer Zahl zu berechnen, importieren wir das in Python integrierte Modul math und verwenden die Funktion math.sqrt().
Da n nicht unbedingt ein perfektes Quadrat ist, müssen wir es in eine ganze Zahl umwandeln. Verwenden Sie int(var), um var in eine ganze Zahl umzuwandeln.
Um sicherzustellen, dass wir tatsächlich bis √n prüfen, fügen wir ein Pluszeichen hinzu, da die Funktion range() den Endpunkt des Bereichs standardmäßig ausschließt.

Die unten stehende Codezelle überprüft, ob unsere Funktion is_prime() korrekt funktioniert.

is_prime(8)
# Falsch

is_prime(15)
# Falsch

is_prime(23)
# Wahr

Im nächsten Abschnitt wollen wir einige einfache Diagramme erstellen, um O(n) und O(√n) visuell zu verstehen.

Visueller Vergleich von O(n) und O(√n)

▶️ Führen Sie den folgenden Codeschnipsel 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(Daten = df)

Der obige Ausschnitt zeigt, wie Sie die Kurven für n und √n für eine Reihe von Werten darstellen können.

Wir verwenden die NumPy-Funktion arange(), um ein Array mit Zahlen zu erstellen.
Und dann sammeln wir die Werte von n und √n bis einschließlich 20 in einem Pandas DataFrame.
Als nächstes verwenden wir die Funktion lineplot() von seaborn.

Aus dem folgenden Diagramm sehen wir, dass √n deutlich kleiner als n ist.

Erhöhen wir nun den Bereich auf bis zu 2000 und wiederholen die gleichen Schritte wie oben.

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(Daten = df)

Aus dem obigen Diagramm können Sie ableiten, dass der O(√n)-Algorithmus deutlich schneller ist, wenn Sie testen, ob eine große Zahl eine Primzahl ist.

Hier ein kurzes Beispiel: 2377 ist eine Primzahl – überprüfen Sie das!😀

Während der O(n)-Ansatz in der Größenordnung von 2000 Schritten liegt, kann der O(√n)-Algorithmus helfen, die Antwort in nur 49 Schritten zu erhalten.✅

Schlussfolgerung

⏳ Und nun ist es Zeit für eine kurze Zusammenfassung.

Um zu prüfen, ob eine Zahl eine Primzahl ist, besteht der naive Ansatz darin, eine Schleife durch alle Zahlen im Bereich (2, n-1) zu ziehen. Wenn Sie keinen Faktor finden, der n teilt, dann ist n eine Primzahl.
Da der einzige Faktor von n, der größer als n/2 ist, n selbst ist, können Sie auch nur bis n/2 laufen.
Beide der oben genannten Ansätze haben eine Zeitkomplexität von O(n).
Da die Faktoren einer Zahl paarweise auftreten, können Sie nur bis √n laufen lassen. Dieser Algorithmus ist viel schneller als O(n). Und der Gewinn ist beträchtlich, wenn Sie prüfen, ob eine große Zahl eine Primzahl ist oder nicht.

Ich hoffe, Sie haben verstanden, wie Sie in Python prüfen können, ob eine Zahl eine Primzahl ist. Als nächsten Schritt können Sie sich unser Tutorial über Python-Programme für String-Operationen ansehen, in demSie lernen, wie Sie prüfen können, ob Strings Palindrome, Anagramme und mehr sind.

Wir sehen uns in einem anderen Lernprogramm wieder. Bis dahin, viel Spaß beim Programmieren! 👩🏽‍💻

Bala Priya C
Beitragender
Bala Priya ist eine indische Entwicklerin und technische Autorin mit mehr als drei Jahren Erfahrung im Schreiben technischer Inhalte. Sie gibt ihr Wissen an die Entwicklergemeinschaft weiter, indem sie technische Tutorials, Anleitungen und mehr schreibt. Derzeit arbeitet sie als technische Redakteurin bei Geekflare. Sie schreibt auch aktiv für verschiedene andere technische Publikationen wie freeCodeCamp und KDnuggets.