Sieve of Eratosthenes

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

It is based on the following observation:

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

Sieve of Eratosthenes

Algorithm

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

• First, list out all the integers [math]\displaystyle{ 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]\displaystyle{ 1 }[/math] is not considered prime; it is ignored.
• Let the smallest prime be [math]\displaystyle{ 2 }[/math]. Since every second number after that will be divisible by [math]\displaystyle{ 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]\displaystyle{ 2 }[/math] and not crossed out. This number is [math]\displaystyle{ 3 }[/math]. We see that [math]\displaystyle{ 3 }[/math] is prime because [math]\displaystyle{ 2 \geq \sqrt{3} }[/math]. Now we cross out every third number which hasn't been crossed out already; these are divisible by [math]\displaystyle{ 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]\displaystyle{ 5 }[/math], so it is also prime. We continue until we reach [math]\displaystyle{ 7 }[/math], and have crossed out all multiples of [math]\displaystyle{ 7 }[/math]. The next prime is [math]\displaystyle{ 11 }[/math], but this is unnecessary because all composite numbers [math]\displaystyle{ 11 \geq \sqrt{N} = 10 \geq \sqrt{k} }[/math] have already been crossed out.

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

Complexity

There are approximately [math]\displaystyle{ \sqrt{N}\over{log\sqrt{N}} }[/math] primes smaller than [math]\displaystyle{ \sqrt{N} }[/math], and for each one we do [math]\displaystyle{ N }[/math] tests. The complexity can thus be bounded by O([math]\displaystyle{ 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.

External links

• Wikipedia