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