Primzahltest mit einem Sieb

Wir überprüfen nun, ob eine bestimmte Zahl N eine Primzahl ist. Und zwar führen wir eine Probedivision durch. Hier ist die Quadratwurzel von N und hier ist die Drei. Beginnend bei drei hüpfen wir in Zweierschritten bis zur Quadratwurzel von N. An jedem Punkt auf dem Weg überprüfen wir, ob dieser Punkt N teilt. Bisher haben die Leute versucht, die Anzahl der Schritte zu reduzieren, indem sie vielleicht später anfangen und größere Schritte machen. Ich möchte hier kurz innehalten und darüber nachdenken, was der ideale Fall für eine Probedivision wäre? Was wäre das Beste, was wir tun könnten, wenn wir sehr kreativ in unseren Schritten wären? Denk daran, jede Zahl N hat eine bestimmte Primfaktorzerlegung. Sagen wir, die Quadratwurzel von N ist hier. Wir müssen tatsächlich nur auf Primzahlen treffen. Das wäre das Beste, was wir tun könnten. Wir wissen, wenn wir nur auf Primzahlen treffen, werden wir schließlich einen Faktor finden. Eine Primfaktorzerlegung, wenn es eine zusammengesetzte Zahl ist. Die Frage ist jetzt, wie effizient ist diese Methode? Es scheint, als hätten wir jetzt eine perfekte Lösung. Wenn wir einen neuen Algorithmus schrieben, der zuerst das Sieb aufruft. Nehmen wir an, der neue Algorithmus berechnet, ob N eine Primzahl ist. Du rufst das Sieb auf und eine schöne lange Liste von Primzahlen wird generiert. Dann haben wir unsere Probedivision, die diese Liste von Primzahlen verwenden würde. Diese würde entlang hüpfen und nur Primzahlen treffen bis zur Quadratwurzel von N, wo immer das ist. Was ist daran falsch? Wir können die Zeitkomplexität oder die Anzahl der ausgeführten Schritte visualisieren. Erinnere dich daran, ich habe das getan, indem ich diesen Algorithmus aufgerufen und einen Schrittzähler in jede Schleife eingebaut habe. Lass uns einfach sagen, Schritt plus plus bedeutet hier Schritt plus eins. In dieser anderen Schleife gibt es auch einen Schrittzähler. Schritt plus plus. Dies sind alles konstante Operationen, die das "if" prüfen und markieren. Wir hatten einfach einen Schrittzähler in jeder Schleife. Hier ist ein Vergleich. Ganz links ist unsere alte Probedivisionsmethode. In der Mitte ist unser Algorithmus, der das Sieb aufruft, um alle Primzahlen bis N zu generieren. Rechts ist dieser Vorschlag, bei dem wir einfach das Sieb aufrufen, um Primzahlen bis zur Quadratwurzel von N zu generieren. Dann wird nur auf diesen Primzahlen eine Probedivision durchgeführt. Lasst uns sehen, was passiert, wenn wir einen kleinen Input haben. Wie wir zunächst sehen, braucht das Sieb viele Schritte. Selbst die modifizierte Version rechts ist tatsächlich langsamer als die Probedivision. Wenn der Input wächst, wächst die Anzahl der Schritte in den Sieben noch schneller. Lasst uns einfach die Mitte vergessen und die Probedivision mit dem Sieb bis zur Quadratwurzel von N plus Probedivision vergleichen. Hier können wir sehen, dass die alte Probedivisionsmethode viel effizienter ist. Die Anzahl der Schritte in unserem Sieb bis zur Quadratwurzel von N plus Probedivision wächst viel schneller. Es ist tatsächlich keine Verbesserung. Unten ist das Programm, das ich verwendet habe, um diesen Vergleich zu machen. Es gibt eine Aufzeichnung, die erklärt, wie ich es eingerichtet habe. Jetzt fragst du dich vielleicht: "Was wäre, wenn wir die Primzahlen im Voraus berechnen würden?" Der erste Schritt wäre, ein Array von Primzahlen zu erstellen und es auf einer Festplatte zu speichern. Dann würde unser Algorithmus nur die Probedivision durchführen und er würde wissen, wie man nur auf Primzahlen hüpft, weil er aus dieser vorgeschlagenen Primzahlliste liest. Vielleicht speichert unsere Primzahlliste alle Primzahlen bis zu 20 Ziffern oder sogar 100 Ziffern. Warum können wir das nicht tun? Das Problem sind die Speicherbegrenzungen. Wenn wir Zahlen auflisten, die wir als nächstes erkunden werden. Nur zum Beispiel: Sagen wir, wir machen das von Hand. Wir nehmen die Zahl Fünf als Primzahl, schreiben es auf ein Blatt Papier und bewahren es in einem Aktenschrank auf. Dann bekommen wir sieben, wir bewahren das im Aktenschrank auf. Neun, oder elf, entschuldigung, in den Aktenschrank. Dann haben wir einen Aktenschrank voller Primzahlen. Stell es dir als ein Primzahlenarray vor. Wie groß wäre dieser Aktenschrank, wenn wir zum Beispiel alle Primzahlen bis zu 20 Ziffern oder alle Primzahlen bis zu 100 Ziffern Länge wollten? Könnten wir dieses Array überhaupt auf einer Festplatte speichern? Um zu verstehen, warum das tatsächlich nicht möglich ist, müssen wir etwas tiefer eintauchen, wie groß dieses Primzahlenarray tatsächlich wird und was die Größenbegrenzung der modernen oder auch zukünftigen Computertechnik ist.