TOPICS
Search

Sieve of Eratosthenes


EratosthenesSieve

An algorithm for making tables of primes. Sequentially write down the integers from 2 to the highest number n you wish to include in the table. Cross out all numbers >2 which are divisible by 2 (every second number). Find the smallest remaining number >2. It is 3. So cross out all numbers >3 which are divisible by 3 (every third number). Find the smallest remaining number >3. It is 5. So cross out all numbers >5 which are divisible by 5 (every fifth number).

Continue until you have crossed out all numbers divisible by |_sqrt(n)_|, where |_x_| is the floor function. The numbers remaining are prime. This procedure is illustrated in the above diagram which sieves up to 50, and therefore crosses out composite numbers up to |_sqrt(50)_|=7. If the procedure is then continued up to n, then the number of cross-outs gives the number of distinct prime factors of each number.

The sieve of Eratosthenes can be used to compute the prime counting function as

 pi(x)=pi(sqrt(x))+1+x-|_1/2x_|-|_1/3x_|-|_1/5x_|-...+|_x/(2·3)_|+|_x/(2·5)_|+|_x/(3...5)_|+...-|_x/(2·3·5)_|+...

which is essentially an application of the inclusion-exclusion principle (Havil 2003, pp. 171-172).


See also

Inclusion-Exclusion Principle, Prime Number, Sieve

Explore with Wolfram|Alpha

References

Conway, J. H. and Guy, R. K. The Book of Numbers. New York: Springer-Verlag, pp. 127-130, 1996.Derbyshire, J. Prime Obsession: Bernhard Riemann and the Greatest Unsolved Problem in Mathematics. New York: Penguin, pp. 100-101, 2004.Flannery, S. and Flannery, D. In Code: A Mathematical Journey. London: Profile Books, pp. 38-42, 2000.Gardner, M. The Sixth Book of Mathematical Games from Scientific American. Chicago, IL: University of Chicago Press, pp. 79-80, 1984.Havil, J. "The Sieve of Eratosthenes." §15.5 in Gamma: Exploring Euler's Constant. Princeton, NJ: Princeton University Press, pp. 171-172, 2003.Haddon, M. The Curious Incident of the Dog in the Night-Time. New York: Vintage, pp. 11-12, 2003.Nagell, T. "General Remarks. The Sieve of Eratosthenes." §15 in Introduction to Number Theory. New York: Wiley, pp. 51-54, 1951.Pappas, T. The Joy of Mathematics. San Carlos, CA: Wide World Publ./Tetra, pp. 100-101, 1989.Ribenboim, P. The New Book of Prime Number Records. New York: Springer-Verlag, pp. 20-21, 1996.Séroul, R. "The Sieve of Eratosthenes." §8.6 in Programming for Mathematicians. Berlin: Springer-Verlag, pp. 169-175, 2000.Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, p. 132, 2002.

Cite this as:

Weisstein, Eric W. "Sieve of Eratosthenes." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/SieveofEratosthenes.html

Subject classifications