A Linear Sieve Algorithm for Finding Prime Numbers

A new algorithm is presented for finding all
primes between 2 and n.  The algorithm executes 
in time proportional to n (assuming that multiplication
of integers not larger than n can be performed 
in unit time).  The method has the same arithmetic complexity
as the algorithm presented by Mairson [6]; 
however, our version is perhaps simpler and more elegant.
 It is also easily extended to find the prime 
factorization of all integers between 2 and n in time proportional to n.   

CACM December, 1978

Gries, D.
Misra, J.

Primes, algorithms, data structures

5.25 5.24 5.29

CA781202 DH January 22, 1979  11:12 AM

2896	4	3037
2972	4	3037
3037	4	3037
3037	4	3037
3039	4	3037
3043	4	3037
3073	4	3037
2732	5	3037
2927	5	3037
3037	5	3037
3037	5	3037
3037	5	3037