Der wichtigste Aspekt hier ist, dass die größte Primzahl, die nicht größer als n ist, ziemlich nahe an n sein muss. Ein kurzer Blick auf The Gaps Between Primes (unter The Prime Pages - immer einen Blick wert für alles, was mit Primzahlen zu tun hat) zeigt, dass für 32-Bit-Zahlen die Abstände zwischen Primzahlen nicht größer als 335 sein können. Dies bedeutet, dass die größte Primzahl nicht größer als n sein muss der Bereich [n - 335, n]. Mit anderen Worten, es müssen höchstens 336 Kandidaten überprüft werden - zum Beispiel durch Probedivision -, und das ist sicher viel schneller als das Sieben einer Milliarde Zahlen.
Die Probenteilung ist eine sinnvolle Wahl für solche Aufgaben, da die zu scannende Reichweite so gering ist. In meiner Antwort auf Prime sieve implementation (using trial division) in C++ analysierte ich ein paar Möglichkeiten, um es zu beschleunigen.
Das Sieb von Eratosthenes ist auch eine gute Wahl, es muss nur modifiziert werden, um nur den interessierenden Bereich zu filtern, statt alle Zahlen von 1 bis n. Dies wird als "Fenster-Sieb" bezeichnet, da nur ein Fenster gesiebt wird. Da das Fenster höchstwahrscheinlich nicht alle Primzahlen bis zur Quadratwurzel von n enthält (dh alle Primzahlen, die potentiell die geringsten Primfaktoren von Kompositen im zu scannenden Bereich sein könnten), ist es am besten, den Faktor Primzahlen überzusieben ein separates, einfaches Sieb von Eratosthenes.
Zuerst zeige ich eine einfache Wiedergabe von normalen (nicht gefenstert) Sieb, als Basis für den Vergleich des gefensterten Codes. Ich benutze C#, um den Algorithmus deutlicher zu zeigen, als es mit Pascal möglich wäre.
Die Funktion hat "klein" in ihrem Namen, weil sie nicht wirklich zum Sieben großer Bereiche geeignet ist; Ich benutze einen ähnlichen Code (mit ein paar Schnickschnack) nur für das Sieben der kleinen Faktor Primzahlen, die von fortgeschritteneren Sieben benötigt werden.
Der Code der gesiebten Primzahlen zur Extraktion ist ebenso einfach:
List<uint> remaining_unmarked_numbers (bool[] eliminated, uint sieve_base)
{
var result = new List<uint>();
for (uint i = 0, e = (uint)eliminated.Length; i < e; ++i)
if (!eliminated[i])
result.Add(sieve_base + i);
return result;
}
nun die Fenster Version. Ein Unterschied besteht darin, dass die potentiellen kleinsten Faktor-Primzahlen getrennt gesiebt werden müssen (durch die gerade gezeigte Funktion), wie zuvor erläutert. Ein weiterer Unterschied besteht darin, dass der Startpunkt der Abtrennsequenz für eine gegebene Primzahl außerhalb des zu siebenden Bereichs liegen kann. Wenn der Startpunkt vor dem Start des Fensters liegt, dann ist ein bisschen Modulo-Magie notwendig, um den ersten "Sprung" zu finden, der im Fenster landet. Von da an verläuft alles wie immer.
List<uint> primes_between (uint m, uint n)
{
m = Math.Max(m, 2);
if (m > n)
return new List<uint>(); // empty range -> no primes
// index overflow in the inner loop unless `(sieve_bits - 1) + stride <= UINT32_MAX`
if (n - m > uint.MaxValue - 65521) // highest prime not greater than sqrt(UINT32_MAX)
throw new ArgumentOutOfRangeException("n", "(n - m) must be <= UINT32_MAX - 65521");
uint sieve_bits = n - m + 1;
var eliminated = new bool[sieve_bits];
foreach (uint prime in small_primes_up_to((uint)Math.Sqrt(n)))
{
uint start = prime * prime, stride = prime;
if (start >= m)
start -= m;
else
start = (stride - 1) - (m - start - 1) % stride;
for (uint j = start; j < sieve_bits; j += stride)
eliminated[j] = true;
}
return remaining_unmarked_numbers(eliminated, m);
}
Die beiden ‚-1‘ Begriffe in der Modulo-Berechnung mag seltsam erscheinen, aber sie spannen die Logik um 1 den unbequemen Fall stride - foo % stride == stride zu beseitigen, die mit auf 0
abgebildet werden müssten dies ist die größte Primzahl wie diese nicht n übersteigt berechnet werden:
uint greatest_prime_not_exceeding (uint n)
{
return primes_between(n - Math.Min(n, 335), n).Last();
}
Dies dauert weniger als eine Millisekunde alles in allem, einschließlich den Sieben des Faktors Primzahlen und so weiter, obwohl der Code enthält keine Optimierung s was auch immer. Einen guten Überblick über anwendbare Optimierungen finden Sie in meiner Antwort auf prime number summing still slow after using sieve; Mit den dort gezeigten Techniken kann der gesamte Bereich bis zu 10^9 in etwa einer halben Sekunde gesiebt werden.
Kompilieren mit aktivierter Optimierung und Bereichsüberprüfung/Überlauferkennung deaktiviert. –