A sublinear additive sieve for finding prime number

Pritchard P. (1981) A sublinear additive sieve for finding prime number. Communications of the ACM, 24 1: 18-23. doi:10.1145/358527.358540


Author Pritchard P.
Title A sublinear additive sieve for finding prime number
Journal name Communications of the ACM
ISSN 1557-7317
Publication date 1981-01-01
Sub-type Article (original research)
DOI 10.1145/358527.358540
Volume 24
Issue 1
Start page 18
End page 23
Total pages 6
Subject 1700 Computer Science
Abstract A new algorithm is presented for the problem of finding all primes between 2 and N. It is based on Mairson's sieve algorithm which uses θ(N) additions and multiplications. The new algorithm improves on this algorithm by using a dynamic sieve technique that avoids most of the nonprimes in the range 2 to N, and by using a tabulation method to simulate multiplications. It is shown to require θ(N/log log N) additions. A related algorithm is outlined that has the same complexity but a storage requirement of only θ(N/log log N) bits.
Keyword algorithms
computational complexity
correctness proofs
prime numbers
sieve
Q-Index Code C1
Q-Index Status Provisional Code
Institutional Status Unknown

Document type: Journal Article
Sub-type: Article (original research)
Collection: Scopus Import
 
Versions
Version Filter Type
Citation counts: Scopus Citation Count Cited 29 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Tue, 09 Aug 2016, 03:24:25 EST by System User