Two compact incremental prime sieves

DOI10.1112/S1461157015000194MaRDI QIDQ3449789zbMATH OpenFDO

Authors Jonathan P. Sorenson

Publication date 5 November 2015

Published in LMS Journal of Computation and Mathematics (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Factorization; primality (11A51) Primality (11Y11) Number-theoretic algorithms; complexity (11Y16) Analysis of algorithms and problem complexity (68Q25)

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.

Recommendations

• scientific article; zbMATH DE number 799788
• Linear prime-number sieves: A family tree
• A space-efficient fast prime number sieve
• Fast compact prime number sieves (among others)
• scientific article; zbMATH DE number 1186941

Cites work

• A space-efficient fast prime number sieve
• A sublinear additive sieve for finding prime number
• An incremental primal sieve
• Approximately counting semismooth integers
• Buckets, Heaps, Lists, and Monotone Priority Queues
• Fast compact prime number sieves (among others)
• scientific article; zbMATH DE number 3657869 (Why is no real title available?)
• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• scientific article; zbMATH DE number 918133 (Why is no real title available?)
• Linear prime-number sieves: A family tree
• Prime sieves using binary quadratic forms
• The Gaussian Law of Errors in the Theory of Additive Number Theoretic Functions
• The segmented sieve of eratosthenes and primes in arithmetic progressions to 1012
• Two fast parallel prime number sieves

Cited in

(7)

• Tabulating Carmichael numbers \(n=Pqr\) with small \(P\)
• scientific article; zbMATH DE number 799788 (Why is no real title available?)
• Inverse sieve
• Algorithmic Number Theory
• Algorithms and bounds on the sums of powers of consecutive primes
• Computation of the least primitive root
• Reducing the space used by the sieve of Eratosthenes when factoring

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)