So erstellen Sie eine Website oder ein Blog im Jahr 2020 - Kostenlose und einfache Anleitung zum Erstellen einer Website

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

In diesem Tutorial erfahren Sie, wie Sie ein Python-Programm schreiben, um zu überprüfen, ob a Zahl ist eine Primzahl Oder nicht.

Wenn Sie jemals an Codierungstests teilgenommen haben, sind Sie beim Primzahltest oder bei der Überprüfung, ob eine Zahl eine Primzahl ist, auf die mathematische Frage gestoßen. Und in den nächsten Minuten erfahren Sie, wie Sie die optimale Lösung für diese Frage finden.

In diesem Tutorial werden Sie:

  • Überprüfen Sie die Grundkonzepte von Primzahlen.
  • 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.

Für all das und mehr, fangen wir an.

Was ist eine Primzahl?

Beginnen wir mit einem Überblick über die Grundlagen der Primzahlen.

In der Zahlentheorie eine natürliche Zahl Norden Leute sagen, dass wesentlich Wenn Sie haben genau zwei Faktoren: 1 und die Zahl selbst (Norden). Erinnern Sie sich aus Ihrer Schulmathematik: eine Zahl Yo Man sagt, es sei ein Faktor der Zahl NordenJa Yo teilen Norden ebenfalls. ✅

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

Norden Faktoren ist er Cousin?
1 1 NEIN
2 1, 2 Ja
3 1, 3 Ja
4 1, 2, 4 NEIN
7 1, 7 Ja
fünfzehn 1, 3, 5, 15 NEIN

Aus der vorherigen Tabelle können wir Folgendes feststellen:

  • 2 ist die kleinste Primzahl.
  • 1 ist ein Faktor jeder Zahl.
  • Jede Zahl n ist ein Faktor ihrer selbst.

Dann sind 1 und n triviale Faktoren für jede Zahl n. Und eine Primzahl sollte nicht mehr Faktoren als diese beiden haben.

Das heißt, wenn Sie von 2 auf – 1 gehen, sollten Sie in der Lage sein, einen nichttrivialen Faktor zu finden, der n ohne Rest teilt.

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

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

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

In Python gibt range(start, stop, step) ein Range-Objekt zurück. Sie können dann über das Bereichsobjekt iterieren, um in Schrittschritten eine Sequenz von Anfang bis Ende -1 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 zusammen mit der for-Schleife verwenden.

Das möchten wir tun:

  • Wenn Sie eine Zahl finden, die teilt Norden gleichmäßig ohne Rest, können Sie sofort schließen, dass die Zahl keine Primzahl ist.
  • Wenn Sie den gesamten Zahlenbereich von durchlaufen haben 2 Den ganzen Weg nach oben n-1 ohne eine Zahl zu finden, die teilt Norden gleichmäßig, dann ist die Zahl eine Primzahl.

Python-Funktion zur Überprüfung von Primzahlen

Mit dem oben Gesagten 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

Lassen Sie uns nun die obige Funktionsdefinition analysieren.

  • Die obige Funktion is_prime() akzeptiert eine positive Ganzzahl Norden wie das Argument.
  • Wenn ein Faktor im angegebenen Bereich von (2, n-1) gefunden wird, gibt die Funktion „Falsch“ zurück, da die Zahl keine Primzahl ist.
  • Und gibt True zurück, wenn die gesamte Schleife durchlaufen wird, ohne einen Faktor zu finden.

Als nächstes rufen wir die Funktion mit Argumenten auf und prüfen, ob die Ausgabe korrekt ist.

is_prime(2)
# True

is_prime(8)
# False

is_prime(9)
# False

is_prime(11)
# True

Im Ergebnis oben 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 noch ein wenig optimieren. Beachten Sie die Liste der Faktoren in der folgenden Tabelle.

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

Nun, wir können sehen, dass das der einzige Faktor ist Norden das ist größer als n/2 Ist Norden selbst.

Das bedeutet also, dass Sie nicht die gesamte Schleife bis n – 1 durchlaufen müssen. Stattdessen können Sie die Schleife nur bis n/2 durchlaufen.

Wenn Sie bis n/2 keinen nichttrivialen Faktor finden, können Sie auch keinen über n/2 hinaus finden.

Jetzt ändern wir die Funktion is_prime(), um die Faktoren im Bereich (2, n/2) zu überprüfen.

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 anhand einiger Funktionsaufrufe überprüfen.

is_prime(9)
# False

is_prime(11)
# True

Obwohl es so aussieht, als hätten wir ihn optimiert, ist dieser Algorithmus hinsichtlich der Komplexität der Ausführungszeit nicht effizienter als der vorherige. Tatsächlich haben beide das getan In) Laufzeitkomplexität: proportional zum Wert von nichtlinear in n.

Können wir es besser machen? Wenn wir können!

▶️ Fahren Sie mit dem nächsten Abschnitt fort, um zu ermitteln, wie Sie die Zeitkomplexität für Primzahltests verbessern können.

O(√n)-Algorithmus zur Überprüfung der Primzahl in Python

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

Ja Zu ist ein Faktor der Zahl NordenEs gibt also auch einen Faktor B so dass axb = nOder 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 das Gleiche auch für weitere Nummern überprüfen, wenn Sie möchten.

Beachten Sie außerdem, dass √18 ungefähr 4,24 beträgt.

Und in den Faktoren, die paarweise auftreten (a,b)Das sieht man ja Zu ist also kleiner als 4,24 B ist größer als 4,24; in diesem Beispiel (2, 18) und (3, 6).

Die folgende Abbildung zeigt die Faktoren von 18, aufgetragen auf der Zahlenlinie.

Wenn sich herausstellt, dass die Zahl n ein perfektes Quadrat ist, haben Sie a = b = √n als einen der Faktoren.

▶️ Schauen Sie sich die Faktoren von 36 in der folgenden Tabelle an. Da 36 ein perfektes Quadrat ist, ist a = b = 6 einer der Faktoren. Für alle anderen Faktorenpaare (a, b) gilt a 6.

Zusammenfassend haben wir Folgendes:

  • jede Zahl Norden Es kann geschrieben werden als n = axb
  • Ja Norden Es ist also ein perfektes Quadrat a = Sekunde = √n.
  • Und wenn einer nach dem anderen, ein und b > n.
  • Ansonsten ja a > bnach a > √n Und zweite .

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

So ändern Sie den is_prime()-Algorithmus in O(√n)

Fahren wir mit der Optimierung der Funktion zum Finden von Primzahlen in Python fort.

import math
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 integrierte Python-Mathematikmodul und verwenden die Funktion math.sqrt().
  • Als Norden Es ist möglicherweise kein perfektes Quadrat, wir müssen es in eine ganze Zahl umwandeln. Verwenden Sie int(var), um var in einen 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() ordnungsgemäß funktioniert.

is_prime(8)
# False

is_prime(15)
# False

is_prime(23)
# True

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

O(n) und O(√n) visuell vergleichen

▶️ Führen Sie den folgenden Codeausschnitt 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)

Der obige Ausschnitt zeigt, wie Sie die Kurven für n und √n für einen Wertebereich zeichnen können.

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

Aus der folgenden Grafik sehen wir, dass √n deutlich kleiner als n ist.

Primzahlen in Python prüfen

Erhöhen wir nun den Bereich auf 2000 und wiederholen die gleichen Schritte 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(data = df)
Primzahlen in Python prüfen

Aus der obigen Grafik können Sie ableiten, dass der O(√n)-Algorithmus deutlich schneller ist, wenn er prüft, ob eine große Zahl eine Primzahl ist.

Hier ein kurzes Beispiel: 2377 ist eine Primzahl, probieren Sie es aus! 😀

Während der O(n)-Ansatz etwa 2000 Schritte erfordert, kann Ihnen der O(√n)-Algorithmus dabei helfen, in nur 49 Schritten zur Antwort zu gelangen.✅

Abschluss

⏳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, der größer als n/2 ist, n selbst ist, können Sie sich dafür entscheiden, nur bis n/2 zu laufen.
  • Beide oben genannten Ansätze haben eine Zeitkomplexität von O(n).
  • Da die Faktoren einer Zahl paarweise vorkommen, kann sie nur bis √n laufen. Dieser Algorithmus ist viel schneller als O(n). Und der Gewinn macht sich bemerkbar, wenn man prü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 in String-Operationen ansehen, in dem Sie lernen, wie Sie überprüfen, ob Strings Palindrome, Anagramme und mehr sind.

Wir sehen uns in einem anderen Tutorial. Bis dahin viel Spaß beim Codieren! 👩🏽‍💻