# Sieve of Eratosthenes

The **sieve of Eratosthenes** is a method to find all prime numbers smaller than a given integer [math]N[/math]. It's invention is credited to the ancient Greek mathematician Eratosthenes.

It is based on the following observation:

- Let [math]N[/math] be a positive integer, and let it's smallest prime factor be [math]a[/math]. If [math]a \leq \sqrt{N}[/math], then [math]N[/math] is composite; otherwise it is prime.

## Algorithm

It is computed as follows; an example is given with [math]N = 100[/math].

- First, list out all the integers [math]1 \leq k \leq N[/math].

- 01 02 03 04 05 06 07 08 09 10
- 11 12 13 14 15 16 17 18 19 20
- 21 22 23 24 25 26 27 28 29 30
- 31 32 33 34 35 36 37 38 39 40
- 41 42 43 44 45 46 47 48 49 50
- 51 52 53 54 55 56 57 58 59 60
- 61 62 63 64 65 66 67 68 69 70
- 71 72 73 74 75 76 77 78 79 80
- 81 82 83 84 85 86 87 88 89 90
- 91 92 93 94 95 96 97 98 99 100

- [math]1[/math] is not considered prime; it is ignored.
- Let the smallest prime be [math]2[/math]. Since every second number after that will be divisible by [math]2[/math], we cross out every second number; all such numbers are composite.

- 01 02 03
~~04~~05~~06~~07~~08~~09~~10~~ - 11
~~12~~13~~14~~15~~16~~17~~18~~19~~20~~ - 21
~~22~~23~~24~~25~~26~~27~~28~~29~~30~~ - 31
~~32~~33~~34~~35~~36~~37~~38~~39~~40~~ - 41
~~42~~43~~44~~45~~46~~47~~48~~49~~50~~ - 51
~~52~~53~~54~~55~~56~~57~~58~~59~~60~~ - 61
~~62~~63~~64~~65~~66~~67~~68~~69~~70~~ - 71
~~72~~73~~74~~75~~76~~77~~78~~79~~80~~ - 81
~~82~~83~~84~~85~~86~~87~~88~~89~~90~~ - 91
~~92~~93~~94~~95~~96~~97~~98~~99~~100~~

- Now we look for the smallest number larger than [math]2[/math] and not crossed out. This number is [math]3[/math]. We see that [math]3[/math] is prime because [math]2 \geq \sqrt{3}[/math]. Now we cross out every third number which hasn't been crossed out already; these are divisible by [math]3[/math] and so are composite.

- 01 02 03
~~04~~05~~06~~07~~08~~~~09~~~~10~~ - 11
~~12~~13~~14~~~~15~~~~16~~17~~18~~19~~20~~ ~~21~~~~22~~23~~24~~25~~26~~~~27~~~~28~~29~~30~~- 31
~~32~~~~33~~~~34~~35~~36~~37~~38~~~~39~~~~40~~ - 41
~~42~~43~~44~~~~45~~~~46~~47~~48~~49~~50~~ ~~51~~~~52~~53~~54~~55~~56~~~~57~~~~58~~59~~60~~- 61
~~62~~~~63~~~~64~~65~~66~~67~~68~~~~69~~~~70~~ - 71
~~72~~73~~74~~~~75~~~~76~~77~~78~~79~~80~~ ~~81~~~~82~~83~~84~~85~~86~~~~87~~~~88~~89~~90~~- 91
~~92~~~~93~~~~94~~95~~96~~97~~98~~~~99~~~~100~~

- The next number not crossed out is [math]5[/math], so it is also prime. We continue until we reach [math]7[/math], and have crossed out all multiples of [math]7[/math]. The next prime is [math]11[/math], but this is unnecessary because all composite numbers [math]11 \geq \sqrt{N} = 10 \geq \sqrt{k}[/math] have already been crossed out.

- In general, for any [math]N[/math], we repeat this process untill the next prime to be tested is larger than [math]\sqrt{N}[/math]. All the number not crossed out are thus prime.

## Complexity

There are approximately [math]\sqrt{N}\over{log\sqrt{N}}[/math] primes smaller than [math]\sqrt{N}[/math], and for each one we do [math]N[/math] tests. The complexity can thus be bounded by O([math]N\sqrt{N}\over{log\sqrt{N}}[/math]). This is a rather loose bound and a better sieve implementation will provide a tighter bound.

The sieve of Eratosthenes has also been adapted to form many faster sieves, like the Atkin Sieve.

The sieve of Eratosthenes is generally used to generate a list of primes for computation of some sort. For example, one may use it to rapidly generate a list of possible Mersenne number exponents to test for primality.