Two compact incremental prime sieves

DOI10.1112/S1461157015000194zbMATH Open1354.11074arXiv1503.02592MaRDI QIDQ3449789

Author name not available (Why is that?)

Publication date: 5 November 2015

Published in: (Search for Journal in Brave)

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 $sqrtn$ space or less. In this paper we present two new results: (1) We describe the rolling sieve, a practical, incremental prime sieve that takes $O(nloglogn)$ time and $O(sqrtnlogn)$ bits of space, and (2) We show how to modify the sieve of Atkin and Bernstein (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.

Full work available at URL: https://arxiv.org/abs/1503.02592

Mathematics Subject Classification ID

No records found.

This page was built for publication: Two compact incremental prime sieves

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