Gegeben n, finde m so, dass m der kleinste Semiprime ist, der größer als n ist.
Nächste Primzahl ist ziemlich einfach, Semiprime ist weniger so. Um es klar zu sagen, es wird nur der Semiprime benötigt, aber es wäre praktisch, die Faktoren gleichzeitig zu bekommen.
Ich habe an einige Ansätze gedacht, aber ich bin mir sicher, dass es bessere gibt.
Arithmetische Operationen werden als O (1) angenommen. Ich habe Sieb von Eratosthenes verwendet, das ist O (n log log n), ich bin mir des Siebes von Atkin bewusst, aber ich mag meine halboptimierten Eratosthenes.
Zähle von n auf, halte an, wenn du einen Semiprime findest.
Das scheint wirklich dumm zu sein, aber wenn es einen O (log n) Semiprime-Test oder einen O (1) -Test gibt, können die Primzahlen unten schneller sein als die anderen 2.
Die Semiprime-Verteilung scheint viel höher zu sein als die Primzahl-Verteilung. Bei einem guten Semi-Prime-Test könnte das sogar besser sein als O (n).
Definieren Sie prev (x) und next (x) und geben Sie jeweils die vorherigen und nächsten Primzahlen an, die O (log n) sein können, wenn die Primzahlen in einem Baum oder mit einer Liste binärer Suche gespeichert sind.
Mach zuerst Sieb.
Beginnen Sie mit p = prev (sqrt (n)) und q = next (n / p). Während pq & lt; = n, gehe zum nächsten q. Wenn pq kleiner als das Minimum ist, notieren Sie es als das neue Minimum. Gehe zum vorherigen p, bis du kein p mehr hast, um zu testen.
Dies wird garantiert die richtige Antwort finden, aber es ist ziemlich langsam. Immer noch O (n log n), also vielleicht akzeptabel.
Beginnen Sie wie gewohnt mit dem Sieb. Erstellen Sie eine Hash-Set-Ansicht des Siebs für O (1) Primalitätstests.
Beginnen Sie mit p = 2. Durchqueren Sie die Primzahlen bis zu sqrt (n). Für jedes p erhält man q = (((n / p + 1) / 2) * 2) +1 = (((n / p + 1)) & gt; 1) & lt; & lt; 1) | 1. Während pq kleiner als das Minimum ist und q nicht prim ist, addiere 2 zu q. Wenn pq immer noch kleiner als das Minimum ist, notieren Sie es als neues Minimum.
Ich habe # 1 und # 3 in Java implementiert, die beide die selbe Sieet-Implementierung von Eratosthenes verwenden. Der größte Teil der Laufzeit wird mit dem Sieben verbracht. Wenn also Optimierungen vorgenommen werden müssen, liegt es im Sieb. Nach einigen Optimierungen schlägt das Hochzählen (# 1) die Primzahlen höher (# 3) und ist im letzten und größten Test (11 Dezimalziffern n) doppelt so schnell.
Es gibt jedoch immer noch Hoffnung, denn wie weit das Sieb verlängert werden muss, hängt von der größten Anzahl der Tests ab. Wenn ein Semiprime-Test mit einer niedrigeren Primer-Testbindung existiert, kann sich die Zählmethode als noch schneller erweisen.
Sicherlich gibt es einen besseren Algorithmus? Oder zumindest eine bessere Möglichkeit, dies zu implementieren?
Hier ist ein Code, der auf meinem obigen Kommentar basiert: Wir werden ein Sieb von Eratosthenes laufen lassen, aber einige zusätzliche Daten speichern, anstatt nur "Prime" oder "nicht" auf der Seite, während wir es tun. Es ist in Haskell, was ich nicht anmerke, ist die am häufigsten verwendete Sprache, also werde ich inline kommentieren, was jedes Bit tut. Zuerst einige Bibliotheksimporte:
%Vor% Wir definieren einen neuen Typ, Primality , mit dem wir bis zu zwei Primfaktoren jeder Zahl speichern können.
Dies besagt, dass es vier Arten von Werten vom Typ Primality gibt: Entweder ist es der Wert Prime , ein Wert der Form OneFactor n für einige unbeschränkte ganze Zahl n , ein Wert der Form TwoFactor n n' für zwei unbeschränkte Ganzzahlen n und n' oder den Wert ManyFactor . Das ist also ein bisschen wie eine Liste von Integer s, die höchstens zwei ganze Zahlen lang ist (oder eine Notiz, die besagt, dass es drei ganze oder lange ganze Zahlen ist). Wir können einer solchen Liste Faktoren hinzufügen:
Wenn man die Liste der Primfaktoren einer Zahl betrachtet, ist es leicht zu überprüfen, ob es sich um einen Semiprimes handelt: Es muss höchstens zwei kleinere Primfaktoren haben, deren Produkt die Zahl selbst ist.
%Vor% Jetzt schreiben wir das Sieb. Nach Bertrands Postulat gibt es für jede n eine Primzahl zwischen n/2 und n ; Das heißt, es gibt einen Semiprime zwischen n und 2n (nämlich zweimal, egal was die Primzahl uns gibt). Außerdem kann ein solcher Semiprime keinen größeren Faktor als n haben (der andere Faktor müsste dann kleiner sein als 2 !). Also filtern wir die Zahlen bis zu 2n nach Faktoren bis zu n und überprüfen dann die Zahlen zwischen n und 2n für Semiprimes. Da diese letzte Überprüfung O (1) ist, fallen wir in den ersten Fall, den Sie vorgeschlagen haben. Also:
Machen Sie ein Array mit Indizes zwischen 2 und 2n , initialisiert auf Prime an jeder Position.
Für jede mögliche Primzahl p zwischen 2 und n ...
... was wir derzeit glauben, ist Prime ...
... fügen Sie p zur Faktorliste für jedes Vielfache von p hinzu.
Führen Sie nun eine lineare Suche nach den verbleibenden Zahlen zwischen n+1 und 2n für einen Semiprime durch. Jeder Aufruf von isSemiprime kostet eine Multiplikation, also sind sie O (1). Technisch kann die Suche fehlschlagen; Die fromJust <$> Annotation sagt dem Compiler, dass wir versprechen, dass es nicht fehlschlägt (weil wir einige Offline-Mathe-Proofs gemacht haben, die zu kompliziert sind, um die Übertragung an den Compiler zu stören).
Das ist der gesamte Körper von nextSemiprime . Es verwendet ein paar Hilfsfunktionen, die wirklich in den Standardbibliotheken irgendwo sein sollten. Der erste ist der lineare Suchalgorithmus; es geht einfach in einer Liste nach einem Element, das ein Prädikat erfüllt.
Die Funktion modifyArray liest nur ein Array-Element und schreibt eine modifizierte Version zurück. Denken Sie an arr[ix] = f(arr[ix]); in C.
Und newSTArray wird benötigt, weil Haskells Behandlung von Arrays unübersichtlich ist: Alle Array-Operationen sind polymorph gegenüber der Art von Array, die Sie verwenden, was gleichzeitig praktisch und ärgerlich ist. Dies sagt dem Compiler, welche Art von Array wir für dieses Programm wollen.
Sie können es hier ausprobieren, was eine einfache main zum Ausdrucken der ersten 100 Halbbilder beinhaltet. (Obwohl diese letztere Aufgabe viel effizienter durchgeführt werden kann, wenn das das Ziel ist!)
Obwohl der aktuelle Algorithmus nur den nächsten Semiprime zurückgibt, ist es einfach, ihn so zu modifizieren, dass er die Faktorisierung des nächsten Semiprime zurückgibt: gib einfach den zugehörigen Primality -Wert zurück und nicht Integer selbst.
Im Anschluss an einen Kommentar (jetzt gelöscht), der zu einem Vorschlag von @DanielWagner gemacht wurde, folgt hier ein nicht optimiertes Semiprime-Sieb, das zwei Bits pro Eintrag verwendet, um eine Anzahl von Faktoren zu behalten.
Der Siebeintrag enthält die Anzahl der gefundenen Faktoren, begrenzt auf 3. Ein Markierstich führt ein Sättigungsinkrement der relevanten Siebeinträge durch.
Da uns zwei gleiche Faktoren wichtig sind, werden auch Primzahlquadrate verwendet. Primzahlen können während des Siebs identifiziert werden, da ihre Faktorzahl 1 ist (Primzahlen haben die Zahl 0; Semi-Primzahlen 2 und andere ganze Zahlen 3). Wenn wir das Quadrat einer Primzahl markieren (was die erste Potenz der Primzahl sein wird), könnten wir jedem Eintrag eine sättigende Addition von zwei hinzufügen, aber als Mikrooptimierung setzt der Code die Zählung einfach auf 3.
Unter der Annahme, dass das Sieb keine Einträge für gerade Zahlen enthält (wie üblich), verwenden wir den Semiprime 4 und alle Semiprime, deren Faktoren 2 und eine ungerade Primzahl sind.
Der folgende Code ist in (Pseudo-) C ++ und zeigt nur, wie die Sieboperation durchgeführt wird. Einige Details, einschließlich der Definition von saturating_increment und den anderen Siebzugriffsfunktionen, wurden weggelassen, da sie offensichtlich sind und nur ablenken.
Hinweis: Ich bin mir bewusst, dass die oben genannten Sweeps Primzahlen aus dem gesamten Bereich verwenden und nicht nur bis zur Quadratwurzel. Das muss etwas kosten, aber ich denke, dass es nur eine Veränderung der Konstante ist. Es ist möglich, den Scan vorzeitig zu beenden und ein bisschen von der Konstante zurückzugewinnen.
Meir-Simchah Panzer schlägt auf Ссылка vor, dass "eine äquivalente Definition dieser Sequenz ... [die] kleinste zusammengesetzte Zahl ist, die ist nicht durch eine kleinere zusammengesetzte Zahl geteilt. "
Hier ist eine Illustration der Berechnung des nächsten Semiprime nach 100, basierend auf dieser Idee:
%Vor%Leute beantworten etwas andere Fragen, also lass mich das in Abschnitte aufteilen.
Gegeben ein Wert n, ist es ein Semiprime. Für kleine Eingaben könnten wir natürlich die Antworten in O (1) vorberechnen und zurückgeben oder suchen. Irgendwann werden wir von Speicheranforderungen überwältigt. Meines Wissens gibt es keine sehr effiziente Lösung für dieses Problem. Es ist dem Primalitäts- oder Quadrat-freien Testen ähnlich, da wir die meisten zufälligen Eingaben mit einfachen Teilbarkeitstests schnell aussortieren können. Angenommen, wir haben einen schnellen Primalitätstest, der einige Vortests enthält, und die meiste Arbeit sucht nur nach einem kleinen Faktor und gibt dann zurück, ob der Rest prim ist. Für Zahlen ohne kleine Faktoren können wir entweder eine Faktorisierung (z.B. Brent / Pollard Rho) oder eine Testteilung bis zu n ^ (1/3) durchführen.
Auf meinem Macbook dauert dies etwa 0,4 Mikrosekunden pro Zahl für den Bereich 1e8 bis 1e7 + 1e7 und weniger als 2 Mikrosekunden pro Zahl für den Bereich 1e16 bis 1e16 + 1e7.
Für große Semi-Primes oder Semi-Primzahlen bin ich mir nicht sicher, ob es eine bessere Lösung gibt, als einen einzelnen Faktor zu finden. Wir benötigen eine Testteilung auf nur N ^ (1/3), aber es gibt effizientere Standard-Factoring-Algorithmen. Einige Implementierungen umfassen Charles Greathouse , mine und viele unter RosettaCode .
Bei 1e16 liegt die durchschnittliche Entfernung zum nächsten Semi-Prime unter 10 und selten über 100. Wenn Sie wie bisher Vorberechnungen durchführen, Speicher verwenden und die Setup-Zeit ignorieren oder amortisieren möchten, kann dies beantwortet werden schnell. Aber wieder einmal nach kleinen Eingaben wird dies sehr umständlich.
Ich glaube nicht, dass Sie nur eine einfache while (1) { n++; if (is_semiprime(n)) return n; } signifikant verbessern können, wenn Sie eine gute is_semiprime-Routine annehmen. Ein komplettes Sieb kommt für mich viel langsamer raus, aber Ihre Laufleistung kann variieren. Es wird wirklich nicht funktionieren, sobald Sie ~ 25-stellige Eingänge überqueren. Sie können leicht optimieren, indem Sie ein Teil-Sieb mit Primzahl-Potenzen machen, das eine Faktor-Zählung erhöht, was bedeutet, dass wir nur den vollen Test auf Ergebnissen durchführen müssen, die offensichtlich nicht halb-prim sind. Ich habe nicht viel Zeit gespart, was sinnvoll ist, da wir nur ein paar native Module ausschneiden. Wenn wir 1000-stellige Eingänge betrachten, dann ist das Teil-Sieb sehr sinnvoll.
Auf meinem Macbook benötigt next_semiprime mit der trivialen is_semiprime-Methode, die nacheinander 1e6-mal beginnend bei 1e8 aufgerufen wird, ungefähr 2 Mikrosekunden pro Aufruf und 17 Mikrosekunden pro Aufruf beim Start bei 1e16.
Einige der Antworten scheinen über diese Frage nachzudenken. Besonders wenn niedrig ist & lt; = 4, dann ist ein Sieb die richtige Antwort. Es gibt schnelle Siebmethoden für Toients und Moebius-Bereiche, ich erwarte, dass Sie eine an die volle Faktoranzahl anpassen können.
Hinweis: Ein gut geschriebenes SoE ist schneller als SoA, also lassen Sie sich nicht von den Leuten ablenken, die das Sieb von Atkin empfehlen, da sie wahrscheinlich nur die ersten Absätze der Wikipedia-Seite gelesen haben. Natürlich werden Details der Implementierungen des Siebs, des Primzahltests und der Vorversuche die Schlussfolgerungen beeinflussen. Ebenso wie die erwarteten Eingabegrößen, Muster und Toleranzen für das Zwischenspeichern von Daten.
Tags und Links algorithm optimization primes sieve-of-eratosthenes primality-test