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:

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

What is a Prime Number?

Beginnen wir damit, die Grundlagen der Primzahlen zu wiederholen.

In der Zahlentheorie eine natürliche Zahl n wird gesagt zuerst wenn ja genau zwei Faktoren: 1 und die Nummer selbst (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.

nFactorsIst Prime?
11Nein
21, 2Ja
31, 3Ja
41, 2, 4Nein
71, 7Ja
151, 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 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) Algorithm to Check if a Number is Prime in Python

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 über das Bereichsobjekt iterieren, 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 eben ohne Rest, können Sie sofort 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 Function to Check for Prime Number

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

How to Optimize the Python Function is_prime()

Hier können wir eine kleine Optimierung vornehmen. Beachten Sie die Liste der Faktoren in der folgenden Tabelle.

NummerFactors
61, 2, 3, 6
101, 2, 5, 10
181, 2, 3, 6, 9, 18

Nun, wir können sehen, dass der einzige Faktor von n das ist größer als n / 2 is n sich.

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 in Bezug auf die Laufzeitkomplexität nicht effizienter als der vorherige. Tatsächlich haben beide 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) Algorithm to Check for Prime Number 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 auch, dass √18 ungefähr 4.24 ist.

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

ab
118
29
36
Faktoren von 18 in Paaren

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

Faktoren auf der Zahlengeraden

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.

ab
136
218
312
49
66
Faktoren von 36 in Paaren

Zusammenfassend haben wir folgendes:

  • Jede Zahl n kann geschrieben werden als n = axb
  • If n ist dann ein perfektes Quadrat 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 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 es math.sqrt() Funktion.
  • As n möglicherweise kein perfektes Quadrat ist, müssen wir es in eine ganze Zahl umwandeln. Benutzen int(var) zu gießen var In ein int.
  • Um sicherzustellen, dass wir tatsächlich bis zu √n prüfen, fügen wir ein Plus als 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 ein paar einfache Diagramme erstellen, um O(n) und O(√n) visuell zu verstehen.

Comparing O(n) and 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 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.

Primzahl-Überprüfung-Python

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)
Primzahl-Überprüfung-Python

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 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!👩🏽‍💻