info prev up next book cdrom email home

Eratosthenes Sieve

\begin{figure}\begin{center}\BoxedEPSF{EratosthenesSieve.epsf scaled 830}\end{center}\end{figure}

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 $\left\lfloor{\sqrt{n}}\right\rfloor $, where $\left\lfloor{x}\right\rfloor $ 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 Primes up to $\left\lfloor{\sqrt{50}}\right\rfloor =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.


References

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

Ribenboim, P. The New Book of Prime Number Records. New York: Springer-Verlag, pp. 20-21, 1996.




© 1996-9 Eric W. Weisstein
1999-05-25