Affordable Access

Publisher Website

A space-efficient fast prime number sieve

Authors
Journal
Information Processing Letters
0020-0190
Publisher
Elsevier
Publication Date
Volume
59
Issue
2
Identifiers
DOI: 10.1016/0020-0190(96)00099-3
Keywords
  • Prime Number Sieve
  • Sieve Of Eratosthenes
  • Number Theoretic Algorithms
  • Analysis Of Algorithms
  • Design Of Algorithms
Disciplines
  • Computer Science
  • Mathematics

Abstract

Abstract We present a new algorithm that finds all primes up to n using at most O( n log log n ) arithmetic operations and O( n (log n log log n) ) space. This algorithm is an improvement of a linear prime number sieve due to Pritchard. Our new algorithm matches the running time of the best previous prime number sieve, but uses less space by a factor of Θ ( log n). In addition, we present the results of our implementations of most known prime number sieves.

There are no comments yet on this publication. Be the first to share your thoughts.