Pritchard's Wheel Sieve [3]

The set Pr(n) of primes less than or equal to n is available after Theta(n/loglogn) operations.

Bengalloun's incremental sieve [1]

The set Pr(n) of primes less than or equal to n is available after O(n) operations. [2]

References

[1] S. Bengalloun, An incremental primal sieve, Acta Informt. 23 (2) (1986) 119-125
[2] Pritchard, P. (1987). Linear prime-number sieves: A family tree. Science of Computer Programming, 9(1), 17–35. https://doi.org/10.1016/0167-6423(87)90024-4 [3] Pritchard, P. (1981). A sublinear additive sieve for finding prime number. Communications of the ACM, 24(1), 18–23. https://doi.org/10.1145/358527.358540

Prime Number Sieves

• Sieve of Eratosthenes
• Pritchard's Wheel Sieve
• Bengalloun's incremental sieve
• Sieve of Atkin