{"id":843033,"date":"2023-09-10T22:55:36","date_gmt":"2023-09-11T03:55:36","guid":{"rendered":"https:\/\/blogging-techies.com\/ge\/so-uberprufen-sie-in-python-ob-eine-zahl-eine-primzahl-ist\/"},"modified":"2023-09-10T22:55:36","modified_gmt":"2023-09-11T03:55:36","slug":"so-uberprufen-sie-in-python-ob-eine-zahl-eine-primzahl-ist","status":"publish","type":"post","link":"https:\/\/blogging-techies.com\/ge\/so-uberprufen-sie-in-python-ob-eine-zahl-eine-primzahl-ist\/","title":{"rendered":"So \u00fcberpr\u00fcfen Sie in Python, ob eine Zahl eine Primzahl ist"},"content":{"rendered":"<p>In diesem Tutorial erfahren Sie, wie Sie ein Python-Programm schreiben, um zu \u00fcberpr\u00fcfen, ob a <strong>Zahl ist eine Primzahl<\/strong> Oder nicht.<\/p>\n<p>Wenn Sie jemals an Codierungstests teilgenommen haben, sind Sie beim Primzahltest oder bei der \u00dcberpr\u00fcfung, ob eine Zahl eine Primzahl ist, auf die mathematische Frage gesto\u00dfen.  Und in den n\u00e4chsten Minuten erfahren Sie, wie Sie die optimale L\u00f6sung f\u00fcr diese Frage finden.<\/p>\n<p>In diesem Tutorial werden Sie:<\/p>\n<ul>\n<li>\u00dcberpr\u00fcfen Sie die Grundkonzepte von Primzahlen.<\/li>\n<li>Schreiben Sie Python-Code, um zu pr\u00fcfen, ob eine Zahl eine Primzahl ist, und <\/li>\n<li>Optimieren Sie es weiter, um einen O(\u221an)-Laufzeitalgorithmus zu erhalten.<\/li>\n<\/ul>\n<p>F\u00fcr all das und mehr, fangen wir an.<\/p>\n<h2 id=\"h-what-is-a-prime-number\">Was ist eine Primzahl?<\/h2>\n<p>Beginnen wir mit einem \u00dcberblick \u00fcber die Grundlagen der Primzahlen. <\/p>\n<p>In der Zahlentheorie eine nat\u00fcrliche Zahl <strong>Norden<\/strong> Leute sagen, dass <strong>wesentlich<\/strong> Wenn Sie haben <strong>genau zwei Faktoren<\/strong>: <strong>1<\/strong> und die Zahl selbst (<strong>Norden<\/strong>).  Erinnern Sie sich aus Ihrer Schulmathematik: eine Zahl <strong>Yo<\/strong> Man sagt, es sei ein Faktor der Zahl <strong>Norden<\/strong>Ja <strong>Yo<\/strong> teilen <strong>Norden<\/strong> ebenfalls.  \u2705<\/p>\n<p>Die folgende Tabelle listet einige Zahlen, alle ihre Faktoren und ob sie Primzahlen sind.<\/p>\n<figure class=\"wp-block-table\">\n<table>\n<tr>\n<td><strong>Norden<\/strong><\/td>\n<td><strong>Faktoren<\/strong><\/td>\n<td><strong>ist er Cousin?<\/strong><\/td>\n<\/tr>\n<tr>\n<td>1<\/td>\n<td>1<\/td>\n<td>NEIN<\/td>\n<\/tr>\n<tr>\n<td>2<\/td>\n<td>1, 2<\/td>\n<td>Ja<\/td>\n<\/tr>\n<tr>\n<td>3<\/td>\n<td>1, 3<\/td>\n<td>Ja<\/td>\n<\/tr>\n<tr>\n<td>4<\/td>\n<td>1, 2, 4<\/td>\n<td>NEIN<\/td>\n<\/tr>\n<tr>\n<td>7<\/td>\n<td>1, 7<\/td>\n<td>Ja<\/td>\n<\/tr>\n<tr>\n<td>f\u00fcnfzehn<\/td>\n<td>1, 3, 5, 15<\/td>\n<td>NEIN<\/td>\n<\/tr>\n<\/table>\n<\/figure>\n<p>Aus der vorherigen Tabelle k\u00f6nnen wir Folgendes feststellen:<\/p>\n<ul>\n<li>2 ist die kleinste Primzahl.<\/li>\n<li>1 ist ein Faktor jeder Zahl.<\/li>\n<li>Jede Zahl n ist ein Faktor ihrer selbst. <\/li>\n<\/ul>\n<p>Dann sind 1 und n triviale Faktoren f\u00fcr jede Zahl n.  Und eine Primzahl sollte nicht mehr Faktoren als diese beiden haben.<\/p>\n<p>Das hei\u00dft, wenn Sie von 2 auf \u2013 1 gehen, sollten Sie in der Lage sein, einen nichttrivialen Faktor zu finden, der n ohne Rest teilt. <\/p>\n<h2 id=\"h-o-n-algorithm-to-check-if-a-number-is-prime-in-python\">O(n)-Algorithmus zur Pr\u00fcfung, ob eine Zahl in Python eine Primzahl ist<\/h2>\n<p>In diesem Abschnitt formalisieren wir den obigen Ansatz in eine Python-Funktion.<\/p>\n<p>Mit dem range()-Objekt in Python k\u00f6nnen Sie alle Zahlen von 2 bis n \u2013 1 durchlaufen. <\/p>\n<p>In Python gibt range(start, stop, step) ein Range-Objekt zur\u00fcck.  Sie k\u00f6nnen dann \u00fcber das Bereichsobjekt iterieren, um in Schrittschritten eine Sequenz von Anfang bis Ende -1 zu erhalten. <\/p>\n<p>Da wir die Menge der ganzen Zahlen von 2 bis n-1 ben\u00f6tigen, k\u00f6nnen wir range(2, n) angeben und es zusammen mit der for-Schleife verwenden.<\/p>\n<p>Das m\u00f6chten wir tun:<\/p>\n<ul>\n<li>Wenn Sie eine Zahl finden, die teilt <strong>Norden<\/strong> gleichm\u00e4\u00dfig ohne Rest, k\u00f6nnen Sie sofort schlie\u00dfen, dass die Zahl keine Primzahl ist. <\/li>\n<\/ul>\n<ul>\n<li>Wenn Sie den gesamten Zahlenbereich von durchlaufen haben <strong>2<\/strong> Den ganzen Weg nach oben <strong>n-1<\/strong> ohne eine Zahl zu finden, die teilt <strong>Norden<\/strong> gleichm\u00e4\u00dfig, dann ist die Zahl eine Primzahl.<\/li>\n<\/ul>\n<h2 id=\"h-python-function-to-check-for-prime-number\">Python-Funktion zur \u00dcberpr\u00fcfung von Primzahlen<\/h2>\n<p>Mit dem oben Gesagten k\u00f6nnen wir fortfahren und die Funktion is_prime() wie folgt definieren.<\/p>\n<pre class=\"wp-block-prismatic-blocks\">def is_prime(n):\n  for i in range(2,n):\n    if (n%i) == 0:\n      return False\n  return True<\/pre>\n<p>Lassen Sie uns nun die obige Funktionsdefinition analysieren.<\/p>\n<ul>\n<li>Die obige Funktion is_prime() akzeptiert eine positive Ganzzahl <strong>Norden<\/strong> wie das Argument.<\/li>\n<li>Wenn ein Faktor im angegebenen Bereich von (2, n-1) gefunden wird, gibt die Funktion \u201eFalsch\u201c zur\u00fcck, da die Zahl keine Primzahl ist.<\/li>\n<li>Und gibt True zur\u00fcck, wenn die gesamte Schleife durchlaufen wird, ohne einen Faktor zu finden.<\/li>\n<\/ul>\n<p>Als n\u00e4chstes rufen wir die Funktion mit Argumenten auf und pr\u00fcfen, ob die Ausgabe korrekt ist.<\/p>\n<pre class=\"wp-block-prismatic-blocks\">is_prime(2)\n# True\n\nis_prime(8)\n# False\n\nis_prime(9)\n# False\n\nis_prime(11)\n# True<\/pre>\n<p>Im Ergebnis oben sehen Sie, dass 2 und 11 Primzahlen sind (die Funktion gibt True zur\u00fcck).  Und 8 und 9 sind keine Primzahlen (die Funktion gibt False zur\u00fcck).<\/p>\n<h2 id=\"h-how-to-optimize-the-python-function-is-prime\">So optimieren Sie die Python-Funktion is_prime() <\/h2>\n<p>Hier k\u00f6nnen wir noch ein wenig optimieren.  Beachten Sie die Liste der Faktoren in der folgenden Tabelle.<\/p>\n<figure class=\"wp-block-table\">\n<table>\n<tr>\n<td><strong>Nummer<\/strong><\/td>\n<td><strong>Faktoren<\/strong><\/td>\n<\/tr>\n<tr>\n<td>6<\/td>\n<td>1, 2, 3, 6<\/td>\n<\/tr>\n<tr>\n<td>10<\/td>\n<td>1, 2, 5, 10<\/td>\n<\/tr>\n<tr>\n<td>18<\/td>\n<td>1, 2, 3, 6, 9, 18<\/td>\n<\/tr>\n<\/table>\n<\/figure>\n<p>Nun, wir k\u00f6nnen sehen, dass das der einzige Faktor ist <strong>Norden<\/strong> das ist gr\u00f6\u00dfer als <strong>n\/2<\/strong> Ist <strong>Norden<\/strong> selbst. <\/p>\n<p>Das bedeutet also, dass Sie nicht die gesamte Schleife bis n \u2013 1 durchlaufen m\u00fcssen. Stattdessen k\u00f6nnen Sie die Schleife nur bis n\/2 durchlaufen. <\/p>\n<p>Wenn Sie bis n\/2 keinen nichttrivialen Faktor finden, k\u00f6nnen Sie auch keinen \u00fcber n\/2 hinaus finden.<\/p>\n<p>Jetzt \u00e4ndern wir die Funktion is_prime(), um die Faktoren im Bereich (2, n\/2) zu \u00fcberpr\u00fcfen.<\/p>\n<pre class=\"wp-block-prismatic-blocks\">def is_prime(n):\n  for i in range(2,int(n\/2)):\n    if (n%i) == 0:\n      return False\n  return True<\/pre>\n<p>Lassen Sie uns fortfahren und die Ausgabe anhand einiger Funktionsaufrufe \u00fcberpr\u00fcfen.<\/p>\n<pre class=\"wp-block-prismatic-blocks\">is_prime(9)\n# False\n\nis_prime(11)\n# True<\/pre>\n<p>Obwohl es so aussieht, als h\u00e4tten wir ihn optimiert, ist dieser Algorithmus hinsichtlich der Komplexit\u00e4t der Ausf\u00fchrungszeit nicht effizienter als der vorherige.  Tats\u00e4chlich haben beide das getan <strong>In)<\/strong> Laufzeitkomplexit\u00e4t: proportional zum Wert von nichtlinear in n.<\/p>\n<p>K\u00f6nnen wir es besser machen?  Wenn wir k\u00f6nnen! <\/p>\n<p>\u25b6\ufe0f Fahren Sie mit dem n\u00e4chsten Abschnitt fort, um zu ermitteln, wie Sie die Zeitkomplexit\u00e4t f\u00fcr Primzahltests verbessern k\u00f6nnen.<\/p>\n<h2 id=\"h-o-n-algorithm-to-check-for-prime-number-in-python\">O(\u221an)-Algorithmus zur \u00dcberpr\u00fcfung der Primzahl in Python<\/h2>\n<p>Es kommt vor, dass die Faktoren einer Zahl paarweise vorkommen. <\/p>\n<p>Ja <strong>Zu<\/strong> ist ein Faktor der Zahl <strong>Norden<\/strong>Es gibt also auch einen Faktor <strong>B<\/strong> so dass <strong>axb = n<\/strong>Oder einfach, <strong>ab = n<\/strong>. <\/p>\n<p>Lassen Sie uns dies anhand eines Beispiels \u00fcberpr\u00fcfen.<\/p>\n<p>Die folgende Tabelle zeigt die paarweise auftretenden Faktoren der Zahl 18.  Sie k\u00f6nnen das Gleiche auch f\u00fcr weitere Nummern \u00fcberpr\u00fcfen, wenn Sie m\u00f6chten. <\/p>\n<p>Beachten Sie au\u00dferdem, dass \u221a18 ungef\u00e4hr 4,24 betr\u00e4gt. <\/p>\n<p>Und in den Faktoren, die paarweise auftreten <strong>(a,b)<\/strong>Das sieht man ja <strong>Zu<\/strong> ist also kleiner als 4,24 <strong>B<\/strong> ist gr\u00f6\u00dfer als 4,24;  in diesem Beispiel (2, 18) und (3, 6).<\/p>\n<figure class=\"wp-block-table\"><\/figure>\n<p>Die folgende Abbildung zeigt die Faktoren von 18, aufgetragen auf der Zahlenlinie.<\/p>\n<figure class=\"wp-block-image size-large\"><\/figure>\n<p>Wenn sich herausstellt, dass die Zahl n ein perfektes Quadrat ist, haben Sie a = b = \u221an als einen der Faktoren.<\/p>\n<p>\u25b6\ufe0f 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\u00fcr alle anderen Faktorenpaare (a, b) gilt a 6.<\/p>\n<figure class=\"wp-block-table\"><\/figure>\n<p>Zusammenfassend haben wir Folgendes:<\/p>\n<ul>\n<li>jede Zahl <strong>Norden<\/strong> Es kann geschrieben werden als <strong>n = axb<\/strong><\/li>\n<li>Ja <strong>Norden<\/strong> Es ist also ein perfektes Quadrat<strong> a = Sekunde = \u221an<\/strong>.<\/li>\n<li>Und wenn <strong>einer nach dem anderen, <strong>ein und <strong>b > n<\/strong>.<\/strong><\/strong><\/li>\n<li>Ansonsten ja <strong>a > b<\/strong>nach <strong>a > \u221an<\/strong> Und <strong>zweite .<\/strong><\/li>\n<\/ul>\n<p>Anstatt also alle ganzen Zahlen bis n\/2 zu durchlaufen, k\u00f6nnen Sie sich auch daf\u00fcr entscheiden, bis zu \u221an zu durchlaufen.  Und das ist viel effizienter als unser bisheriger Ansatz. <\/p>\n<h3 id=\"h-how-to-modify-is-prime-to-o-n-algorithm\">So \u00e4ndern Sie den is_prime()-Algorithmus in O(\u221an)<\/h3>\n<p>Fahren wir mit der Optimierung der Funktion zum Finden von Primzahlen in Python fort.<\/p>\n<pre class=\"wp-block-prismatic-blocks\">import math\ndef is_prime(n):\n  for i in range(2,int(math.sqrt(n))+1):\n    if (n%i) == 0:\n      return False\n  return True<\/pre>\n<p>Lassen Sie uns nun die obige Funktionsdefinition analysieren:<\/p>\n<ul>\n<li>Um die Quadratwurzel einer Zahl zu berechnen, importieren wir das integrierte Python-Mathematikmodul und verwenden die Funktion math.sqrt(). <\/li>\n<li>Als <strong>Norden<\/strong> Es ist m\u00f6glicherweise kein perfektes Quadrat, wir m\u00fcssen es in eine ganze Zahl umwandeln.  Verwenden Sie int(var), um var in einen int umzuwandeln.<\/li>\n<li>Um sicherzustellen, dass wir tats\u00e4chlich bis zu \u221an pr\u00fcfen, f\u00fcgen wir ein Plus eins hinzu, da die Funktion range() standardm\u00e4\u00dfig den Endpunkt des Bereichs ausschlie\u00dft.<\/li>\n<\/ul>\n<p>Die folgende Codezelle \u00fcberpr\u00fcft, ob unsere Funktion is_prime() ordnungsgem\u00e4\u00df funktioniert.<\/p>\n<pre class=\"wp-block-prismatic-blocks\">is_prime(8)\n# False\n\nis_prime(15)\n# False\n\nis_prime(23)\n# True<\/pre>\n<p>Im n\u00e4chsten Abschnitt erstellen wir einige einfache Diagramme, um O(n) und O(\u221an) visuell zu verstehen.<\/p>\n<h2 id=\"h-comparing-o-n-and-o-n-visually\">O(n) und O(\u221an) visuell vergleichen<\/h2>\n<p>\u25b6\ufe0f F\u00fchren Sie den folgenden Codeausschnitt in einer Jupyter-Notebook-Umgebung Ihrer Wahl aus.<\/p>\n<pre class=\"wp-block-prismatic-blocks\">import numpy as np\nimport seaborn as sns\nimport pandas as pd\n\n\nn = 20\n\nx = np.arange(n)\ny1 = np.sqrt(x)\ny2 = x\ndf = pd.DataFrame({\"O(\u221an)\":y1,\"O(n)\":y2})\nsns.set_theme()\nsns.lineplot(data = df)\n<\/pre>\n<p>Der obige Ausschnitt zeigt, wie Sie die Kurven f\u00fcr n und \u221an f\u00fcr einen Wertebereich zeichnen k\u00f6nnen.<\/p>\n<ul>\n<li>Wir verwenden die NumPy-Funktion arange(), um ein Array von Zahlen zu erstellen. <\/li>\n<li>Und dann sammeln wir die Werte von n und \u221an bis einschlie\u00dflich 20 in einem Pandas-DataFrame.<\/li>\n<li>Als n\u00e4chstes zeichnen wir mit der Funktion lineplot() von Seaborn.<\/li>\n<\/ul>\n<p>Aus der folgenden Grafik sehen wir, dass \u221an deutlich kleiner als n ist.<\/p>\n<figure class=\"wp-block-image size-full\"><img decoding=\"async\" loading=\"lazy\" width=\"383\" height=\"251\" alt=\"Primzahlen in Python pr\u00fcfen\" class=\"wp-image-88382 perfmatters-lazy\" src=\"https:\/\/miblogging.com\/bloggingtechies\/wp-content\/uploads\/2022\/06\/prime-number-python-1.png\" data-=\"\"><\/figure>\n<p>Erh\u00f6hen wir nun den Bereich auf 2000 und wiederholen die gleichen Schritte oben.<\/p>\n<pre class=\"wp-block-prismatic-blocks\">import numpy as np\nimport seaborn as sns\nimport pandas as pd\n\n\nn = 2000\n\nx = np.arange(n)\ny1 = np.sqrt(x)\ny2 = x\ndf = pd.DataFrame({\"O(\u221an)\":y1,\"O(n)\":y2})\nsns.set_theme()\nsns.lineplot(data = df)\n<\/pre>\n<figure class=\"wp-block-image size-full\"><img decoding=\"async\" loading=\"lazy\" width=\"386\" height=\"251\" alt=\"Primzahlen in Python pr\u00fcfen\" class=\"wp-image-88383 perfmatters-lazy\" src=\"https:\/\/miblogging.com\/bloggingtechies\/wp-content\/uploads\/2022\/06\/prime-number-python-2.png\" data-=\"\"><\/figure>\n<p>Aus der obigen Grafik k\u00f6nnen Sie ableiten, dass der O(\u221an)-Algorithmus deutlich schneller ist, wenn er pr\u00fcft, ob eine gro\u00dfe Zahl eine Primzahl ist. <\/p>\n<p>Hier ein kurzes Beispiel: 2377 ist eine Primzahl, probieren Sie es aus!  \ud83d\ude00 <\/p>\n<p>W\u00e4hrend der O(n)-Ansatz etwa 2000 Schritte erfordert, kann Ihnen der O(\u221an)-Algorithmus dabei helfen, in nur 49 Schritten zur Antwort zu gelangen.\u2705<\/p>\n<h3 id=\"h-conclusion\">Abschluss<\/h3>\n<p>\u23f3Und es ist Zeit f\u00fcr eine kurze Zusammenfassung.<\/p>\n<ul>\n<li>Um zu \u00fcberpr\u00fcfen, 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.<\/li>\n<li>Da der einzige Faktor von n, der gr\u00f6\u00dfer als n\/2 ist, n selbst ist, k\u00f6nnen Sie sich daf\u00fcr entscheiden, nur bis n\/2 zu laufen.<\/li>\n<li>Beide oben genannten Ans\u00e4tze haben eine Zeitkomplexit\u00e4t von O(n).<\/li>\n<li>Da die Faktoren einer Zahl paarweise vorkommen, kann sie nur bis \u221an laufen.  Dieser Algorithmus ist viel schneller als O(n).  Und der Gewinn macht sich bemerkbar, wenn man pr\u00fcft, ob eine gro\u00dfe Zahl eine Primzahl ist oder nicht.<\/li>\n<\/ul>\n<p>Ich hoffe, Sie verstehen, wie man in Python pr\u00fcft, ob eine Zahl eine Primzahl ist.  Als n\u00e4chsten Schritt k\u00f6nnen Sie sich unser Tutorial zu Python-Programmen in String-Operationen ansehen, in dem Sie lernen, wie Sie \u00fcberpr\u00fcfen, ob Strings Palindrome, Anagramme und mehr sind. <\/p>\n<p>Wir sehen uns in einem anderen Tutorial.  Bis dahin viel Spa\u00df beim Codieren!  \ud83d\udc69\ud83c\udffd\u200d\ud83d\udcbb<\/p>\n   ","protected":false},"excerpt":{"rendered":"<p>In diesem Tutorial erfahren Sie, wie Sie ein Python-Programm schreiben, um zu \u00fcberpr\u00fcfen, ob a Zahl ist eine Primzahl Oder nicht. Wenn Sie jemals an Codierungstests teilgenommen haben, sind Sie beim Primzahltest oder bei der \u00dcberpr\u00fcfung, ob eine Zahl eine Primzahl ist, auf die mathematische Frage gesto\u00dfen. Und in den n\u00e4chsten Minuten erfahren Sie, wie [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":843034,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":"","fifu_image_url":"https:\/\/blogging-techies.com\/wp-content\/uploads\/2023\/06\/3-1.jpg","fifu_image_alt":""},"categories":[7],"tags":[],"_links":{"self":[{"href":"https:\/\/blogging-techies.com\/ge\/wp-json\/wp\/v2\/posts\/843033"}],"collection":[{"href":"https:\/\/blogging-techies.com\/ge\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogging-techies.com\/ge\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogging-techies.com\/ge\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blogging-techies.com\/ge\/wp-json\/wp\/v2\/comments?post=843033"}],"version-history":[{"count":0,"href":"https:\/\/blogging-techies.com\/ge\/wp-json\/wp\/v2\/posts\/843033\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/blogging-techies.com\/ge\/wp-json\/wp\/v2\/media\/843034"}],"wp:attachment":[{"href":"https:\/\/blogging-techies.com\/ge\/wp-json\/wp\/v2\/media?parent=843033"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogging-techies.com\/ge\/wp-json\/wp\/v2\/categories?post=843033"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogging-techies.com\/ge\/wp-json\/wp\/v2\/tags?post=843033"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}