Der bekannteste Algorithmus zum Auffinden aller Primzahlen, die nicht größer als eine bestimmte sind, ist das Eratosthenes-Sieb . Es funktioniert hervorragend für Zahlen bis zu Milliarden, vielleicht bis zu zehn Milliarden, wenn es ordentlich geschrieben ist. Jeder, der Spaß mit Primzahlen haben möchte, weiß jedoch, dass Sie immer so viele wie möglich zur Hand haben möchten. Um ein Problem mit einem Hackerrank zu lösen, brauchte ich einmal eine In-Memory-Datenbank mit Primzahlen von bis zu hundert Milliarden. Wenn das Eratosthenes-Sieb bei maximaler Speicheroptimierung ungerade Zahlen mit einem Bit-Array aufweist, beträgt seine Größe etwa 6 Gigabyte, was nicht in den Speicher meines Laptops passt. Es gibt eine Modifikation des Algorithmus, die im Speicher viel weniger anspruchsvoll ist (Aufteilen des ursprünglichen Zahlenbereichs in mehrere Teile und Verarbeiten von jeweils einem Teil) -segmentiertes Sieb von Eratosthenes , aber es ist schwieriger zu implementieren, und das gesamte Ergebnis wird sowieso nicht in den Speicher passen. Im Folgenden möchte ich Sie auf einen Algorithmus aufmerksam machen, der fast so einfach ist wie das Eratosthenes-Sieb, aber eine doppelte Optimierung durch den Speicher ermöglicht (dh eine Datenbank mit Primzahlen von bis zu einhundert Milliarden belegt etwa 3 Gigabyte, die bereits in den Speicher eines Standard-Laptops passen sollten).Zunächst erinnern wir uns daran, wie das Sieb von Eratosthenes funktioniert: In einer Reihe von Zahlen von 1 bis N werden durch zwei teilbare Zahlen durchgestrichen, dann durch 3 teilbare Zahlen und so weiter. Die nach dem Durchstreichen verbleibenden Zahlen sind einfach:2 3 . 5 . 7 . 9 . 11 . 13 . 15 . 17 . 19 . 21 . 23 . 25 . 27 . 29 ...
2 3 . 5 . 7 . . . 11 . 13 . . . 17 . 19 . . . 23 . 25 . . . 29 ...
2 3 . 5 . 7 . . . 11 . 13 . . . 17 . 19 . . . 23 . . . . . 29 ...
C # -Codeclass EratospheneSieve
{
private bool[] Data;
public EratospheneSieve(int length)
{
Data = new bool[length];
for (int i = 2; i < Data.Length; i++) Data[i] = true;
for (int i = 2; i * i < Length; i++)
{
if (!Data[i]) continue;
for (int d = i * i; d < Length; d += i) Data[d] = false;
}
}
public int Length => Data.Length;
public bool IsPrime(int n) => Data[n];
}
Auf meinem Laptop zählt es bis zu 15 Milliarden Sekunden und verbraucht ein Gigabyte Speicher.Der Algorithmus, den wir verwenden werden, heißt Radfaktorisierung . Um seine Essenz zu verstehen, schreiben wir natürliche Zahlen mit einer Tafel mit 30 Teilen hintereinander: 0 1 2 3 4 5 ... 26 27 28 29
30 31 32 33 34 35 ... 56 57 58 59
60 61 62 63 64 65 ... 86 87 88 89
...
Und streichen Sie alle durch 2, 3 und 5 teilbaren Zahlen durch:. 1 . . . . . 7 . . . 11 . 13 . . . 17 . 19 . . . 23 . . . . . 29
. 31 . . . . . 37 . . . 41 . 43 . . . 47 . 49 . . . 53 . . . . . 59
. 61 . . . . . 67 . . . 71 . 73 . . . 77 . 79 . . . 83 . . . . . 89
...
Es ist ersichtlich, dass in jeder Zeile die Nummern an den gleichen Positionen durchgestrichen sind. Da wir nur zusammengesetzte Zahlen durchgestrichen haben (mit Ausnahme der Zahlen 2, 3, 5), können Primzahlen nur an nicht markierten Positionen stehen.Da jede Zeile acht solcher Zahlen enthält, haben wir die Idee, jeweils dreißig Zahlen mit einem Byte darzustellen, von denen jedes der acht Bits die Einfachheit der Zahl an der entsprechenden Position anzeigt. Dieser Zufall ist nicht nur ästhetisch schön, sondern vereinfacht auch die Implementierung des Algorithmus erheblich!
Technische Umsetzung
Erstens ist es unser Ziel, einhundert Milliarden zu erreichen, sodass auf vier Byte-Zahlen nicht mehr verzichtet werden kann. Daher sieht unser Algorithmus ungefähr so aus:class Wheel235
{
private byte[] Data;
public Wheel235(long length)
{
...
}
public bool IsPrime(long n)
{
...
}
...
}
Zur Vereinfachung der Implementierung runden wir die Länge auf die nächste durch 30 teilbare Zahl auf. Dannclass Wheel235
{
private byte[] Data;
public Wheel235(long length)
{
length = (length + 29) / 30 * 30;
Data = new byte[length/30];
...
}
public long Length => Data.Length * 30L;
...
}
Als nächstes benötigen wir zwei Arrays: eines übersetzt den Index 0..29 in die Bitnummer, das zweite im Gegenteil die Bitnummer in die Position dreißig. Mit diesen Arrays und etwas Bitarithmetik erstellen wir eine Eins-zu-Eins-Entsprechung zwischen natürlichen Zahlen und Bits im Datenarray. Der Einfachheit halber verwenden wir nur zwei Methoden: IsPrime (n), mit dem Sie herausfinden können, ob die Zahl eine Primzahl ist, und ClearPrime (n), mit dem das entsprechende Bit auf 0 gesetzt wird, wobei die Zahl n als Verbindung markiert wird:class Wheel235
{
private static int[] BIT_TO_INDEX = new int[] { 1, 7, 11, 13, 17, 19, 23, 29 };
private static int[] INDEX_TO_BIT = new int[] {
-1, 0,
-1, -1, -1, -1, -1, 1,
-1, -1, -1, 2,
-1, 3,
-1, -1, -1, 4,
-1, 5,
-1, -1, -1, 6,
-1, -1, -1, -1, -1, 7,
};
private byte[] Data;
...
public bool IsPrime(long n)
{
if (n <= 5) return n == 2 || n == 3 || n == 5;
int bit = INDEX_TO_BIT[n % 30];
if (bit < 0) return false;
return (Data[n / 30] & (1 << bit)) != 0;
}
private void ClearPrime(long n)
{
int bit = INDEX_TO_BIT[n % 30];
if (bit < 0) return;
Data[n / 30] &= (byte)~(1 << bit);
}
}
Beachten Sie, dass wenn die Zahl durch 2, 3 oder 5 teilbar ist, die Bitnummer -1 ist, was bedeutet, dass die Zahl offensichtlich zusammengesetzt ist. Nun, und natürlich verarbeiten wir einen Sonderfall n <= 5.Nun tatsächlich der Algorithmus selbst, der das Sieb von Eratosthenes fast buchstäblich wiederholt: public Wheel235(long length)
{
length = (length + 29) / 30 * 30;
Data = new byte[length / 30];
for (long i = 0; i < Data.Length; i++) Data[i] = byte.MaxValue;
for (long i = 7; i * i < Length; i++)
{
if (!IsPrime(i)) continue;
for (long d = i * i; d < Length; d += i) ClearPrime(d);
}
}
Dementsprechend ist die gesamte resultierende Klasse:sieht so ausclass Wheel235
{
private static int[] BIT_TO_INDEX = new int[] { 1, 7, 11, 13, 17, 19, 23, 29 };
private static int[] INDEX_TO_BIT = new int[] {
-1, 0,
-1, -1, -1, -1, -1, 1,
-1, -1, -1, 2,
-1, 3,
-1, -1, -1, 4,
-1, 5,
-1, -1, -1, 6,
-1, -1, -1, -1, -1, 7,
};
private byte[] Data;
public Wheel235(long length)
{
length = (length + 29) / 30 * 30;
Data = new byte[length / 30];
for (long i = 0; i < Data.Length; i++) Data[i] = byte.MaxValue;
for (long i = 7; i * i < Length; i++)
{
if (!IsPrime(i)) continue;
for (long d = i * i; d < Length; d += i) ClearPrime(d);
}
}
public long Length => Data.Length * 30L;
public bool IsPrime(long n)
{
if (n >= Length) throw new ArgumentException("Number too big");
if (n <= 5) return n == 2 || n == 3 || n == 5;
int bit = INDEX_TO_BIT[n % 30];
if (bit < 0) return false;
return (Data[n / 30] & (1 << bit)) != 0;
}
private void ClearPrime(long n)
{
int bit = INDEX_TO_BIT[n % 30];
if (bit < 0) return;
Data[n / 30] &= (byte)~(1 << bit);
}
}
Es gibt nur ein kleines Problem: Dieser Code funktioniert nicht für Zahlen größer als etwa 65 Milliarden! Wenn Sie versuchen, es mit solchen Zahlen zu starten, stürzt das Programm mit einem Fehler ab:Unhandled Exception: System.OverflowException: Array dimensions exceeded supported range.
Das Problem ist, dass in c # Arrays nicht mehr als 2 ^ 31 Elemente enthalten können (anscheinend, weil die interne Implementierung einen 4-Byte-Array-Index verwendet). Eine Möglichkeit besteht darin, beispielsweise ein langes [] Array anstelle eines Byte [] Arrays zu erstellen. Dies erschwert jedoch die Bitarithmetik ein wenig. Der Einfachheit halber gehen wir in die andere Richtung und erstellen eine spezielle Klasse, die das gewünschte Array simuliert und zwei kurze Arrays enthält. Gleichzeitig geben wir ihm die Möglichkeit, uns auf der Festplatte zu speichern, damit Sie Primzahlen einmal berechnen und dann die Datenbank erneut verwenden können: class LongArray
{
const long MAX_CHUNK_LENGTH = 2_000_000_000L;
private byte[] firstBuffer;
private byte[] secondBuffer;
public LongArray(long length)
{
firstBuffer = new byte[Math.Min(MAX_CHUNK_LENGTH, length)];
if (length > MAX_CHUNK_LENGTH) secondBuffer = new byte[length - MAX_CHUNK_LENGTH];
}
public LongArray(string file)
{
...
}
public long Length => firstBuffer.LongLength + (secondBuffer == null ? 0 : secondBuffer.LongLength);
public byte this[long index]
{
get => index < MAX_CHUNK_LENGTH ? firstBuffer[index] : secondBuffer[index - MAX_CHUNK_LENGTH];
set
{
if (index < MAX_CHUNK_LENGTH) firstBuffer[index] = value;
else secondBuffer[index - MAX_CHUNK_LENGTH] = value;
}
}
public void Save(string file)
{
...
}
}
Kombinieren Sie abschließend alle Schritte inendgültige Version des Algorithmusclass Wheel235
{
class LongArray
{
const long MAX_CHUNK_LENGTH = 2_000_000_000L;
private byte[] firstBuffer;
private byte[] secondBuffer;
public LongArray(long length)
{
firstBuffer = new byte[Math.Min(MAX_CHUNK_LENGTH, length)];
if (length > MAX_CHUNK_LENGTH) secondBuffer = new byte[length - MAX_CHUNK_LENGTH];
}
public LongArray(string file)
{
using(FileStream stream = File.OpenRead(file))
{
long length = stream.Length;
firstBuffer = new byte[Math.Min(MAX_CHUNK_LENGTH, length)];
if (length > MAX_CHUNK_LENGTH) secondBuffer = new byte[length - MAX_CHUNK_LENGTH];
stream.Read(firstBuffer, 0, firstBuffer.Length);
if(secondBuffer != null) stream.Read(secondBuffer, 0, secondBuffer.Length);
}
}
public long Length => firstBuffer.LongLength + (secondBuffer == null ? 0 : secondBuffer.LongLength);
public byte this[long index]
{
get => index < MAX_CHUNK_LENGTH ? firstBuffer[index] : secondBuffer[index - MAX_CHUNK_LENGTH];
set
{
if (index < MAX_CHUNK_LENGTH) firstBuffer[index] = value;
else secondBuffer[index - MAX_CHUNK_LENGTH] = value;
}
}
public void Save(string file)
{
using(FileStream stream = File.OpenWrite(file))
{
stream.Write(firstBuffer, 0, firstBuffer.Length);
if (secondBuffer != null) stream.Write(secondBuffer, 0, secondBuffer.Length);
}
}
}
private static int[] BIT_TO_INDEX = new int[] { 1, 7, 11, 13, 17, 19, 23, 29 };
private static int[] INDEX_TO_BIT = new int[] {
-1, 0,
-1, -1, -1, -1, -1, 1,
-1, -1, -1, 2,
-1, 3,
-1, -1, -1, 4,
-1, 5,
-1, -1, -1, 6,
-1, -1, -1, -1, -1, 7,
};
private LongArray Data;
public Wheel235(long length)
{
length = (length + 29) / 30 * 30;
Data = new LongArray(length / 30);
for (long i = 0; i < Data.Length; i++) Data[i] = byte.MaxValue;
for (long i = 7; i * i < Length; i++)
{
if (!IsPrime(i)) continue;
for (long d = i * i; d < Length; d += i) ClearPrime(d);
}
}
public Wheel235(string file)
{
Data = new LongArray(file);
}
public void Save(string file) => Data.Save(file);
public long Length => Data.Length * 30L;
public bool IsPrime(long n)
{
if (n >= Length) throw new ArgumentException("Number too big");
if (n <= 5) return n == 2 || n == 3 || n == 5;
int bit = INDEX_TO_BIT[n % 30];
if (bit < 0) return false;
return (Data[n / 30] & (1 << bit)) != 0;
}
private void ClearPrime(long n)
{
int bit = INDEX_TO_BIT[n % 30];
if (bit < 0) return;
Data[n / 30] &= (byte)~(1 << bit);
}
}
Als Ergebnis haben wir eine Klasse erhalten, die Primzahlen von nicht mehr als einhundert Milliarden berechnen und das Ergebnis auf der Festplatte speichern kann (ich hatte diesen Code 50 Minuten lang auf meinem Laptop; die Größe der erstellten Datei betrug erwartungsgemäß etwa 3 Gigabyte): long N = 100_000_000_000L;
Wheel235 wheel = new Wheel235(N);
wheel.Save("./primes.dat");
Und dann von der Festplatte lesen und verwenden: DateTime start = DateTime.UtcNow;
Wheel235 loaded = new Wheel235("./primes.dat");
DateTime end = DateTime.UtcNow;
Console.WriteLine($"Database of prime numbers up to {loaded.Length:N0} loaded from file to memory in {end - start}");
long number = 98_000_000_093L;
Console.WriteLine($"{number:N0} is {(loaded.IsPrime(number) ? "prime" : "not prime")}!");