Sundarama Sieb

Das Sundarama-Sieb im Netzwerk wird durch eine Vielzahl von Quellen mit kurzen Hintergrundinformationen dargestellt. Trotzdem habe ich mich entschlossen, zu Beginn des Studiums der zahlentheoretischen Algorithmen anzugeben, was ich selbst lesen möchte.

Das Sundarama-Sieb ist eine der drei bekanntesten Methoden zur Erzeugung von Primzahlen. Jetzt ist es üblich, es wegen der geringen Rechenkomplexität als exotisch zu behandeln: O (N (logN)). Asymptotika sind jedoch asymptotisch, und in der Praxis überholt Atkin beispielsweise im 32-Bit-Siebbereich Sundaram nur mit sorgfältiger Optimierung.

Die im Internet verbreiteten Implementierungen des Atkin-Siebs übertreffen das Sundaram-Sieb weder zeitlich noch in Bezug auf die Speichereffizienz. So kann die Sundaram-Methode als Hilfsmittel bei Experimenten mit fortgeschritteneren Algorithmen verwendet werden.

Das Sundarama-Sieb findet alle Primzahlen in einem gegebenen Bereich natürlicher Zahlen 3 ≤ n ≤ N, wobei die Komponenten "herausgesiebt" werden. Ohne Verlust der Allgemeinheit kann der Wert von N als ungerade angesehen werden. Wenn N gerade ist, ist es garantiert zusammengesetzt, und es kann aus dem Siebbereich ausgeschlossen werden, indem der Wert der oberen Grenze um eins verringert wird.

Der Algorithmus basiert auf der folgenden Tatsache. Jede ungerade zusammengesetzte Zahl n kann als Produkt zweier natürlicher ungerader Zahlen größer als eins dargestellt werden:

(1) n = (2 · i + 1) · (2 ​​· j + 1),

wobei i und j natürliche Zahlen sind (Null ist keine natürliche Zahl). Es ist unmöglich, sich eine Primzahl n in dieser Form vorzustellen, da dies sonst bedeuten würde, dass n neben sich und einem zusätzliche Teiler hat.

Wir schreiben das ungerade n in der Form 2 * m + 1, setzen es in (1) ein und erhalten den Ausdruck für m:

(2) m = 2 · i · j + i + j.

Diese Transformation führt direkt zur Idee des Siebs von Sundaram.

Um zusammengesetzte Zahlen aus einem bestimmten Intervall auszusondern, sollten Sie ein Array verwenden, in dem ein Element mit dem Index m für die Zahl 2 * m + 1 steht. Nachdem Sie die Aufzählung der Werte der Variablen i und j organisiert haben, berechnen wir den Index m nach der Formel (2) und im entsprechenden Array-Elemente setzen die Markierung "Composite Number". Nach Abschluss der Aufzählung werden alle zusammengesetzten Zahlen im Bereich markiert, und Primzahlen können durch Fehlen einer Markierung ausgewählt werden.

Es bleibt die technische Details zu klären.

Basierend auf der vorherigen Überlegung nimmt der Index m zur Darstellung der oberen (ungeraden) Grenze des Siebbereichs N seinen Maximalwert mmax = (N - 1) / 2 an. Dies bestimmt die erforderliche Größe des Arrays.

Wir werden die Werte von i und j in zwei Zyklen aufzählen: eine äußere Schleife zum Aufzählen der Werte von i und eine verschachtelte innere Schleife für die Werte von j.

Der Anfangswert des externen Schleifenzählers ist i = 1. Angesichts der vollständigen Symmetrie des Auftretens der Variablen i und j in Ausdruck (2) sollte der interne Zyklus mit dem Wert j = i beginnen, um wiederholte Doppelberechnungen zu vermeiden.

Finden Sie den Maximalwert für den externen Schleifenzähler imax ≥ i. Wenn die Grenze des Bereichs N eine ungerade zusammengesetzte Zahl ist, muss mit dem Wert i = imax die innere Schleife mindestens einmal mit dem Wert ihres Parameters j = imax ausgeführt werden, um N zu löschen, und Ausdruck (2) nimmt seinen Maximalwert an:

mmax = 2 * imax * imax + imax + imax,
imax ^ 2 + imax - mmax / 2 = 0.

Wenn wir diese quadratische Gleichung lösen, erhalten wir: imax = (√ (2 * mmax + 1) -1) / 2 = (√N-1) / 2.
Die Einschränkung für den Zähler des inneren Zyklus jmax ≥ j ergibt sich aus der Ungleichung
mmax ≥ 2 * i * j + i + j , woher wir erhalten: jmax = (mmax - i) / (2 * i + 1).

Die Werte der Obergrenzen sollten auf den nächsten Gesamtwert gerundet werden, wobei der Bruchteil verworfen wird.

Das Folgende ist eine Auflistung einer sehr einfachen C # Sundaram-Klasse, die die beschriebene Methode implementiert.

using System; using System.Collections; namespace CSh_Sundaram { public class Sundaram { public double dt; //   () private long t1; //   private long t2; //   private uint limit; //     private int arrlength; //   private BitArray Prim; //    private int counter; public Sundaram(uint _limit) { limit = _limit; if (limit % 2 == 0) limit -= 1; arrlength = (int)(limit / 2); Prim = new BitArray(arrlength); t1 = DateTime.Now.Ticks; Sieve(); //  t2 = DateTime.Now.Ticks; dt = (double)(t2 - t1) / 10000000D; counter = -1; } public uint NextPrime { get { while (counter < arrlength - 1) { counter++; if (!Prim[counter]) return (uint)(2 * counter + 3); } return 0; } } private void Sieve() { int imax = ((int)Math.Sqrt(limit) - 1) / 2; for (int i = 1; i <= imax; i++) { int jmax = (arrlength - i) / (2 * i + 1); for (int j = i; j <= jmax; j++) { Prim[2 * i * j + i + j - 1] = true; } } } } } 

Als Parameter beim Erstellen eines Objekts vom Typ Sundaram wird die Obergrenze des Siebbereichs angegeben. Zum Sieben verwendet die Klasse ein Array vom Typ BitArray. Dies erhöht die Laufzeit, ermöglicht es Ihnen jedoch, den gesamten 32-Bit-Bereich des Uint-Typs abzudecken. Das Sieben wird ausgeführt, wenn vom Klassenkonstruktor aus auf die Sieve () -Methode zugegriffen wird. Nach seiner Fertigstellung enthält das Feld dt die Siebausführungszeit in Sekunden.

Beim Zugriff auf die NextPrime-Eigenschaft werden nacheinander ab 3 in aufsteigender Reihenfolge Primzahlen zurückgegeben. Nachdem alle einfachen aus dem Bereich erschöpft sind, wird der Wert 0 zurückgegeben.