A linear sieve algorithm for finding prime numbers
Authors:
Open Access
- 1 December 1978
- journal article
- Published by Association for Computing Machinery (ACM) in Communications of the ACM
- Vol. 21 (12) , 999-1003
Abstract
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 .Keywords
This publication has 5 references indexed in Scilit:
- The Multiple Assignment StatementIEEE Transactions on Software Engineering, 1978
- Some new upper bounds on the generation of prime numbersCommunications of the ACM, 1977
- Guarded commands, nondeterminacy and formal derivation of programsCommunications of the ACM, 1975
- Riemann's Hypothesis and tests for primality1975
- Class number, a theory of factorization, and genera1971