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