The I/O complexity of computing prime tables

Michael A. Bender, Rezaul Chowdhury, Alexander Conway, Martín Farach-Colton, Pramod Ganapathi, Rob Johnson, Samuel McCauley, Bertrand Simon, Shikha Singh

    Research output: Chapter in Book/Report/Conference proceedingConference contribution


    We revisit classical sieves for computing primes and analyze their performance in the external-memory model. Most prior sieves are analyzed in the RAM model, where the focus is on minimizing both the total number of operations and the size of the working set. The hope is that if the working set fits in RAM, then the sieve will have good I/O performance, though such an outcome is by no means guaranteed by a small working-set size. We analyze our algorithms directly in terms of I/Os and operations. In the external-memory model, permutation can be the most expensive aspect of sieving, in contrast to the RAM model, where permutations are trivial. We show how to implement classical sieves so that they have both good I/O performance and good RAM performance, even when the problem size N becomes huge—even superpolynomially larger than RAM. Towards this goal, we give two I/O-efficient priority queues that are optimized for the operations incurred by these sieves.

    Original languageEnglish (US)
    Title of host publicationLATIN 2016
    Subtitle of host publicationTheoretical Informatics - 12th Latin American Symposium, Proceedings
    EditorsGonzalo Navarro, Evangelos Kranakis, Edgar Chávez
    PublisherSpringer Verlag
    Number of pages15
    ISBN (Print)9783662495285
    StatePublished - 2016
    Event12th Latin American Symposium on Theoretical Informatics, LATIN 2016 - Ensenada, Mexico
    Duration: Apr 11 2016Apr 15 2016

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349


    Conference12th Latin American Symposium on Theoretical Informatics, LATIN 2016


    • External-memory algorithms
    • Prime tables
    • Priority queues
    • Sorting

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • General Computer Science


    Dive into the research topics of 'The I/O complexity of computing prime tables'. Together they form a unique fingerprint.

    Cite this