Key points are not available for this paper at this time.
Gegeben eine ganze Zahl N, wie hoch ist die Berechnungskomplexität, um alle Primzahlen kleiner als N zu finden? Ein modifiziertes Sieb von Eratosthenes, das doppelt verkettete Listen verwendet, ergibt einen Algorithmus mit einer arithmetischen Komplexität von O A (N). Diese obere Schranke wird als äquivalent zur theoretischen unteren Schranke für Siebmöglichkeiten ohne Vorverarbeitung gezeigt. Der Einsatz von Vorverarbeitungstechniken, die Raum-Zeit- und additive-multiplikative Kompromisse umfassen, reduziert diese obere Schranke auf O A (N/log logN) und die Bitkomplexität auf O B (N logN log log logN). Ein Speicherbedarf wird ebenfalls mit O B (N logN/log logN) Bits beschrieben.
Harry G. Mairson (Do,) untersuchte diese Frage.