Effiziente Speicherung von Primzahlen

Question

Für eine Bibliothek muss ich die ersten Primzahlen bis zu einem Limit L speichern. Diese Sammlung muss eine O (1) Lookup-Zeit haben (um zu überprüfen, ob eine Zahl prim ist oder nicht) und es Es muss einfach sein, die nächste Primzahl zu finden (vorausgesetzt, sie ist kleiner als L).

Angesichts L ist fixiert, ein Eratostene Sieb, um die Liste zu erstellen, ist in Ordnung. Im Moment verwende ich ein gepacktes Boolesches Array, um die Liste zu speichern, die nur Einträge für ungerade Zahlen zwischen 3 und L (inklusive) enthält. Dies benötigt (L-2)/2 Speicherbits. Ich möchte in der Lage sein, L statisch zu erhöhen, ohne mehr Speicher zu verwenden.

Gibt es eine Datenstruktur, die weniger Speicher mit ähnlichen Eigenschaften verwendet? Oder mit mindestens der konstanten Nachschlagezeit? (Ungerade Zahlen können dann aufgezählt werden, bis wir eine erstklassige bekommen)

(die Sprache, die ich schrieb dies in ist Factor aber diese Frage wäre das gleiche in jeder Sprache sein, die oder leicht programmierbar gepackten Bit-Arrays in-gebaut hat)

Answer 1

Sie können explizit mehrere Primzahlen überprüfen, um die Redundanz zu entfernen.

Im Moment tun Sie dies nur für zwei, indem Sie explizit die Teilbarkeit durch zwei prüfen und dann nur für ungerade Zahlen speichern, ob sie Primzahlen sind.

Für 2 und 3 erhalten Sie die Reste 0 bis 5, von denen nur 1 und 5 nicht durch zwei oder drei teilbar sind und zu einer Primzahl führen können, also sind Sie auf 1/3 runter.

Für 2, 3 und 5 erhalten Sie 8 Zahlen aus 30, die in einem Byte gespeichert werden können.

Dies wird näher erläutert here.

Answer 2

Wenn Sie herausfinden können, welche Mersenne oder andere leicht darstellbare Primzahlen sind, können Sie möglicherweise ein paar Bits speichern, indem Sie diese Darstellung mit einem Flag für anwendbare Zahlen verwenden.

Wie wäre es mit dem Speichern der Nummern als Unterschied zur vorherigen Nummer? Dann sollte die Größe nicht ganz so schnell ansteigen (aber Lookup wäre langsam). In Kombination mit dem obigen Ansatz konnten Sie Mersenne-Primzahlen und den Unterschied zum letzten Mersenne-Prime speichern.

Answer 3

Angesichts der Tatsache, dass Speicher so billig ist, glaube ich nicht, dass Sie aus einer Geschwindigkeitsperspektive viel besser als Ihr vorhandenes Schema tun können.

Wenn es eine bessere Lösung ist, dann gehe ich davon würde es Vorteil der Prime Number Theorem nehmen würde, das zeigt, dass als L wird größer, die Grenze von

π (L)/(L/ln (L)) Ansätze 1.

Vielleicht wäre eine bessere Lösung eine adaptive Packungslösung in einer Datenstruktur wie ein skip list.

Answer 4

Vielleicht ist eine trie Datenstruktur, die nur die Primzahlen enthält, was Sie suchen. Anstatt Zeichen als Indizes zu verwenden, können Sie die Integer-Ziffern verwenden. Eine Implementierung davon sind Judy-Array s.

Obwohl sie nicht Ihre O (1) Anforderung erfüllen, sind sie äußerst speichereffizient für ähnliche Schlüssel (wie die meisten Teile von Zahlen) und ziemlich schnell mit einem O (m) nachzuschlagen (m = Schlüssel Länge) maximal.

Wenn Sie im vorgenerierten Baum nach einer Primzahl suchen, können Sie den Baum so lange laufen lassen, bis Sie ihn finden, oder Sie befinden sich bereits an dem Knoten, der neben dem vorangehenden und folgenden Prim befindet.

Answer 5

Momentan behandeln Sie 2 als Spezialfall und haben dann ein Array, in dem jede ungerade Zahl einem Element im Array zugeordnet wird (wobei einige ungerade Zahlen Primzahlen sind). Sie könnten dies verbessern, indem Sie 2 und 3 als Sonderfälle behandeln und erkennen, dass der Rest der Primzahlen in der Form 6n + 1 oder 6n-1 ist (dh für alle Primzahlen p mit p> 3, p mod 6 = 1 oder 5). Dies kann weiter verallgemeinert werden - siehe Wikipedia. Für alle Primzahlen p> 5, p mod 30 = 1, 7, 11, 13, 17, 19, 23 oder 29. Sie könnten damit fortfahren und den Speicherbedarf auf Kosten der Bearbeitungszeit reduzieren (obwohl es noch sein wird O (1), nur ein langsamer O (1)).

Answer 6

Wie wäre es mit einer Art Hashtabelle?

Sie müssten eine sehr gute Hash-Funktion (so etwas wie n mod p, wo p nicht ein Vielfaches von einem der q niedrigsten Primzahlen - wählen q ausreichend hoch, um die Anzahl der Kollisionen zu minimieren).

Answer 7

Eine Alternative zu gepackten Bitmaps und Rädern - in bestimmten Zusammenhängen aber ebenso effizient - ist die Speicherung der Unterschiede zwischen aufeinander folgenden Primzahlen. Wenn Sie wie üblich die Zahl 2 weglassen, sind alle Unterschiede gleich. Speichern von Differenz/2 Sie können bis zu 2^40ish Regionen (kurz vor 1999066711391) mit Byte-Größe Variablen.

Die Primes up 2^32 benötigen nur 194 MByte, verglichen mit 256 MByte für eine Odds-Only-Bitmap. Das Iterieren über Delta-gespeicherte Primes ist viel schneller als bei einem Radlager, das das Modulo-2-Rad, das als Odds-Only-Bitmap bekannt ist, umfasst.

Für Bereiche ab 1999066711391 sind größere Zellen oder Speicher mit variabler Länge erforderlich. Letzteres kann äußerst effizient sein, selbst wenn sehr einfache Schemata verwendet werden (z. B. Hinzufügen eines Byte < 255, wie in LZ4-style-Komprimierung), wegen der extrem niedrigen Häufigkeit von Lücken, die länger als 510/2 sind.

Aus Gründen der Effizienz ist es am besten, den Bereich in Abschnitte (Seiten) zu teilen und sie B-Tree-Stil zu verwalten.

Entropie-Codierung die Unterschiede (Huffmann oder arithmetische Codierung) schneidet dauerhafte Speicheranforderungen auf etwas weniger als die Hälfte, die in der Nähe der theoretischen optimalen und besser als Listen oder Räder komprimiert mit den besten verfügbaren Packer.

Wenn die Daten unkomprimiert gespeichert werden, ist es immer noch viel kompakter als Dateien mit binären oder textuellen Zahlen, um eine Größenordnung oder mehr. Mit einem B-Tree-Style-Index ist es einfach, Abschnitte nach Bedarf in den Speicher zu mappen und mit höchster Geschwindigkeit über sie hinweg zu iterieren.

Answer 8

die TopCoder-Tutorial auf Primzahlen Check: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=math_for_topcoders

Answer 9

Wie über einen Intervall-Baum? http://www.geeksforgeeks.org/interval-tree/

Es kann nicht O (1) sein, aber es ist sehr schnell. Wie vielleicht O (log (p (n))) wobei p (n) die Anzahl der Primzahlen bis zur Zahl n ist. Auf diese Weise wird der Speicher, den Sie benötigen, proportional zur Anzahl der Primzahlen sein, wodurch die Speicherkosten stark reduziert werden.Nehmen wir zum Beispiel an, Sie finden eine Primzahl bei p1 und dann die nächste bei p2, Fügen Sie das Intervall (p1, p2) usw. ein und wenn Sie nach einer Zahl in diesem Bereich suchen, wird dieses Intervall zurückgegeben und Sie können p2 zurückgeben, was in Ihrem Fall die Antwort wäre.