So prüfen Sie, ob eine Zahl in Python eine Primzahl ist

In diesem Tutorial lernen Sie, wie Sie ein Python-Programm schreiben, um zu überprüfen, ob a Zahl ist Primzahl 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:

• revdie Grundlagen der Primzahlen betrachten,
• 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.

Was ist eine Primzahl?

Beginnen wir mit revDie Grundlagen der Primzahlen erläutern.

In der Zahlentheorie eine natürliche Zahl n wird gesagt zuerst wenn ja genau zwei Faktoren: 1 und die Nummer esself (n). Erinnern Sie sich an Ihre Schulmathematik: eine Zahl i soll ein Faktor der Zahl sein nWenn i teilt n gleichmäßig. ✅

Die folgende Tabelle listet einige Zahlen auf, alle ihre Faktoren und ob sie Primzahlen sind.

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 davonself.

Also sind 1 und n 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 auf n – 1 gehen, sollten Sie nicht in der Lage sein, einen nicht-trivialen Faktor zu finden, der n ohne Rest teilt.

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

Lassen Sie uns in diesem Abschnitt den obigen Ansatz in einer Python-Funktion formalisieren.

Mit können Sie alle Zahlen von 2 bis n – 1 durchlaufen range() Objekt in Python.

In Python range(start, stop, step) gibt ein Bereichsobjekt zurück. Sie können dann iterierenate über das Bereichsobjekt, um eine Sequenz zu erhalten start den ganzen Weg bis zu stop -1 in Schritten von step.

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

Folgendes möchten wir tun:

• Wenn Sie eine Zahl finden, die teilbar ist n Gleichmäßig ohne Rest, Sie können sofort weitermachenateDaraus lässt sich schließen, dass die Zahl keine Primzahl ist.

• Wenn Sie den gesamten Nummernbereich aus durchgeschleift haben 2 den ganzen Weg bis zu n - 1 ohne eine Zahl zu finden, die teilbar ist n eben, dann ist die Zahl eine Primzahl.

Python-Funktion zur Prüfung auf Primzahlen

Mit dem Obigen können wir fortfahren und die Funktion definieren is_prime() wie folgt.

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 eine positive ganze Zahl an n als Argument.
• Wenn Sie einen Faktor im angegebenen Bereich von (2, n-1) finden, kehrt die Funktion zurück False– da die Zahl keine Primzahl ist.
• Und es kehrt zurück True 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 zurück True). Und 8 und 9 sind keine Primzahlen (die Funktion gibt zurück False).

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.

Nun, wir können sehen, dass der einzige Faktor von n das ist großartigater als n / 2 is n itself.

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.

Jetzt ändern wir die Funktion is_prime() nach Faktoren im Bereich (2, n/2) 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 nicht effizienter als der prevwas die Laufzeitkomplexität betrifft. Tatsächlich haben beide das getan O (n) Laufzeitkomplexität: 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 Primzahlen in Python

Es kommt vor, dass die Faktoren einer Zahl paarweise auftreten.

If a ist ein Faktor der Zahl n, 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 außerdem, dass √18 ein Näherungswert istateJuli 4.24.

Und in den paarweise auftretenden Faktoren (a, b), das sieht man wenn a kleiner als 4.24 ist, dann b ist grater als 4.24 – in diesem Beispiel (2, 18) und (3, 6).

Die folgende Abbildung zeigt die Faktoren von 18, aufgetragen auf dem Zahlenstrahl.

Wenn die Zahl n zufällig ein Perfekt ist square, hast du a = b = √n als einen der Faktoren.

▶️ Schau dir die Faktoren von 36 in der Tabelle unten an. Da 36 ein Perfekt ist square, a = b = 6 ist einer der Faktoren. Für alle anderen Faktorpaare (a, b) gilt a < 6 und b > 6.

Zusammenfassend haben wir folgendes:

• Jede Zahl n kann geschrieben werden als n = axb
• If n ist ein perfekter square und dann a = b = √n.
• Und wenn a < b, dann, a < √n und b > √n.
• Sonst ggf a > b und dann a > √n und b < √n.

Anstatt also alle ganzen Zahlen bis n/2 zu durchlaufen, können Sie sich auch dafür entscheiden, bis √n zu laufen. Und das ist viel effizienter als unser previous 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 zu berechnen square Wurzel einer Zahl, lassen Sie uns das eingebaute Mathematikmodul von Python importieren und verwenden math.sqrt() Funktion.
• As n kann nicht perfekt sein square, müssen wir es in eine Ganzzahl umwandeln. Verwenden int(var) zu gießen var In ein int.
• Um sicherzustellen, dass wir aktiv sindally Wenn wir bis zu √n prüfen, fügen wir ein Plus eins hinzu range() -Funktion schließt standardmäßig den Endpunkt des Bereichs aus.

Die folgende Codezelle bestätigt, dass unsere Funktion is_prime() funktioniert richtig.

is_prime(8)
# False

is_prime(15)
# False

is_prime(23)
# True

Lassen Sie uns im nächsten Abschnitt erstellenate ein paar einfache Diagramme zum Verständnis von O(n) und O(√n) visuellally.

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

▶️ Führen Sie das folgende Code-Snippet in a aus Jupyter Notizbuch Umwelt von Ihre Wahl.

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 NumPy-Funktion arange() zum Erstellenate eine Reihe von Zahlen.
• 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.✅

Schlussfolgerung

⏳ 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.
• Als einziger Faktor von n greater als n/2 ist n itself, 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 ansehen Python-Programme für String-Operationen– wo 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!👩🏽‍💻