Sieve of Eratosthenes

An Algorithm for making tables of Primes. Sequentially write down the Integers from 2 to thehighest number you wish to include in the table. Cross out all numbers which are divisible by 2 (every secondnumber). Find the smallest remaining number . It is 3. So cross out all numbers which are divisible by 3 (everythird number). Find the smallest remaining number . It is 5. So cross out all numbers which are divisible by 5(every fifth number).

Continue until you have crossed out all numbers divisible by , where is the FloorFunction. The numbers remaining are Prime. This procedure is illustrated in the above diagram which sieves up to 50,and therefore crosses out Primes up to . If the procedure is then continued up to , then the numberof cross-outs gives the number of distinct Prime factors of each number.

References

Conway, J. H. and Guy, R. K. The Book of Numbers. New York: Springer-Verlag, pp. 127-130, 1996.

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.

• Function Field
• Function Space
• Functor
• Fundamental Class
• Fundamental Continuity Theorem
• Fundamental Discriminant
• Fundamental Forms
• Fundamental Group
• Fundamental Homology Class
• Fundamental Lemma of Calculus of Variations
• Fundamental System
• Fundamental Theorem of Algebra
• Fundamental Theorem of Arithmetic
• Fundamental Theorem of Curves
• Fundamental Theorem of Directly Similar Figures
• Fundamental Theorem of Gaussian Quadrature
• Fundamental Theorem of Genera
• Fundamental Theorem of Plane Curves
• Fundamental Theorem of Projective Geometry
• Fundamental Theorem of Space Curves
• Fundamental Theorem of Symmetric Functions
• Fundamental Theorems of Calculus
• Fundamental Unit
• Funnel
• Fuss's Problem