sieve of Eratosthenes SieveOfEratosthenes 2002-05-22 23:27:14 2004-11-22 19:39:57 Definition % this is the default PlanetMath preamble. as your knowledge % of TeX increases, you will probably want to edit this, but % it should be fine as is for beginners. % almost certainly you want these \usepackage{amssymb} \usepackage{amsmath} \usepackage{amsfonts} % used for TeXing text within eps files %\usepackage{psfrag} % need this for including graphics (\includegraphics) %\usepackage{graphicx} % for neatly defining theorems and propositions %\usepackage{amsthm} % making logically defined graphics %\usepackage{xypic} % there are many more packages, add them here as you need them % define commands here The \emph{sieve of Eratosthenes} is a simple algorithm for generating a list of the prime numbers between $1$ and some integer $N\geq 2$. Let $p=2$, which is of course known to be prime. Mark all positive multiples of $p$ (e.g. $2, 4, 6, 8 \dots$), up until $N$, as composite. Now let $p$ be the smallest number not marked as composite (in this case, $3$); it must be the next prime. Again, mark all positive multiples of $p$ as composite. Continue this process while $p \leq \sqrt{N}$. When done, all numbers less than $N$ that have not been marked as composite are prime. For many years, the sieve of Eratosthenes was the fastest known algorithm for listing primes. Today, there are faster methods, such as a quadratic sieve.