A SPACE-EFFICIENT FAST PRIME NUMBER SIEVE

Authors
DUNTEN B JONES J SORENSON J
Citation
B. Dunten et al., A SPACE-EFFICIENT FAST PRIME NUMBER SIEVE, Information processing letters, 59(2), 1996, pp. 79-84
Citations number
16
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
59
Issue
2
Year of publication
1996
Pages
79 - 84
Database
ISI
SICI code
0020-0190(1996)59:2<79:ASFPNS>2.0.ZU;2-B
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 p revious prime number sieve, but uses less space by a factor of Theta(l og n). In addition, we present the results of our implementations of m ost known prime number sieves.