Some New Upper Bounds on the Generation of Prime Numbers

Given an integer N, what is the computational
complexity of finding all the primes less than 
N?  A modified sieve of Eratosthenes using doubly linked
lists yields an algorithm of O(N) arithmetic 
complexity.  This upper bound is shown to be equivalent
to the theoretical lower bound for sieve methods 
without preprocessing.  Use of preprocessing techniques
involving space-time and additive-multiplicative 
tradeoffs reduces this upper bound to O(N/log logN)
and the bit complexity to O(N logN log log logN). 
 A storage requirement is described using O(N logN/log logN) bits as well.

CACM September, 1977

Mairson, H. G.

computational complexity, sieve, prime number generation,
number theory, linked list, preprocessing, 
balancing

5.25 5.39

CA770907 JB December 27, 1977  12:55 PM

1841	4	2927
1841	4	2927
1967	4	2927
2120	4	2927
2120	4	2927
2927	4	2927
2927	4	2927
2927	4	2927
2927	4	2927
2927	4	2927
1537	5	2927
1538	5	2927
1539	5	2927
1841	5	2927
1840	5	2927
2927	5	2927
2927	5	2927
2927	5	2927
3037	5	2927
2732	6	2927
2927	6	2927