![](https://d3ilqtpdwi981i.cloudfront.net/zAtIZmfjEodYau7-hAyp8o5gEW0=/425x550/smart/https://bepress-attached-resources.s3.amazonaws.com/uploads/4d/18/d0/4d18d083-4987-46ce-bfef-9b9a75a19e6c/thumbnail_f9556a87-2d9f-497c-b584-43855f7a3e28.jpg)
Article
Two Compact Incremental Prime Sieves
LMS Journal of Computation and Mathematics
Document Type
Article
Publication Date
1-1-2015
Disciplines
DOI
https://doi.org/10.1112/S1461157015000194
Abstract
A prime sieve is an algorithm that finds the primes up to a bound n. We say that a prime sieve is incremental, if it can quickly determine if n+1 is prime after having found all primes up to n. We say a sieve is compact if it uses roughly √n space or less. In this paper, we present two new results.
- We describe the rolling sieve, a practical, incremental prime sieve that takes O(n log log n) time and O(√n log n) bits of space.
- We also show how to modify the sieve of Atkin and Bernstein from 2004 to obtain a sieve that is simultaneously sublinear, compact, and incremental.
The second result solves an open problem given by Paul Pritchard in 1994.
Rights
This is a pre-print version of this article. The version of record is available at Cambridge University Press.
NOTE: this version of the article is pending revision and may not reflect the changes made in the final, peer-reviewed version.
Citation Information
Jonathan P Sorenson. "Two Compact Incremental Prime Sieves" LMS Journal of Computation and Mathematics Vol. 18 Iss. 1 (2015) p. 675 - 683 Available at: http://works.bepress.com/jonathan_sorenson/12/