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.

Statistics

Seen <100 times
0 Comments

More articles like this

Fast compact prime number sieves (among others)

on Journal of Algorithms Jan 01, 1983

2 Fast Parallel Prime Number Sieves

on Information and Computation Jan 01, 1994

Linear prime-number sieves: A family tree

on Science of Computer Programmin... Jan 01, 1987
More articles like this..