The I/O complexity of computing prime tables

DOI10.1007/978-3-662-49529-2_15MaRDI QIDQ2802940zbMATH OpenOpenAlexFDO

Authors Alexander Conway, Martin Farach-Colton, Pramod Ganapathi, Rob Johnson, Samuel McCauley, Bertrand Simon, Shikha Singh, Michael A. Bender, Rezaul Alam Chowdhury

Publication date 3 May 2016

Published in LATIN 2016: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL https://hal.inria.fr/hal-01326317/file/sieve.pdf

zbMATH Keywords

external-memory algorithmsprime tablespriority queuessorting

Mathematics Subject Classification ID

Primality (11Y11) Number-theoretic algorithms; complexity (11Y16) Searching and sorting (68P10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40)

Recommendations

• On the importance of cache tuning in a cache-aware algorithm: a case study
• Two fast parallel prime number sieves
• Worst-case efficient external-memory priority queues
• scientific article; zbMATH DE number 1186941

Cited in

(2)

• The red-blue pebble game on trees and DAGs with large input
• On the importance of cache tuning in a cache-aware algorithm: a case study

This page was built for publication: The I/O complexity of computing prime tables

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2802940)