| Currently there may be errors shown on top of a page, because of a missing Wiki update (PHP version and extension DPL3). |
| Topics | Register • News • History • How to • Sequences statistics • Template prototypes |
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.
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
04050607080910 - 11
121314151617181920 - 21
222324252627282930 - 31
323334353637383940 - 41
424344454647484950 - 51
525354555657585960 - 61
626364656667686970 - 71
727374757677787980 - 81
828384858687888990 - 91
9293949596979899100
- 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
04050607080910 - 11
121314151617181920 21222324252627282930- 31
323334353637383940 - 41
424344454647484950 51525354555657585960- 61
626364656667686970 - 71
727374757677787980 81828384858687888990- 91
9293949596979899100
- 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.
