A practical sieve algorithm finding prime numbers

ABSTRACT

Based on the sieve of Eratosthenes, a faster and more compact algorithm is presented for finding all primes between 2 and N.

REFERENCES

• 1: Edsger W. Dijkstra, Guarded commands, nondeterminacy and formal derivation of programs, Communications of the ACM, v.18 n.8, p.453-457, Aug. 1975 [doi>10.1145/360933.360975]
• 2: David Gries , Jayadev Misra, A linear sieve algorithm for finding prime numbers, Communications of the ACM, v.21 n.12, p.999-1003, Dec. 1978 [doi>10.1145/359657.359660]
• 3: Knuth, D. The Alt of Computer Programming. Vol. 2, 2d ed. 1981, p. 394.
• 4: Harry G. Mairson, Some new upper bounds on the generation of prime numbers, Communications of the ACM, v.20 n.9, p.664-669, Sept. 1977 [doi>10.1145/359810.359838]
• 5: Paul Pritchard, A sublinear additive sieve for finding prime number, Communications of the ACM, v.24 n.1, p.18-23, Jan. 1981 [doi>10.1145/358527.358540]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Number-theoretic computations (e.g., factoring, primality testing)

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Tables**; Arrays

  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Efficiency

General Terms:
Algorithms, Performance, Theory