# sieve of Eratosthenes

(algorithm)

Definition: An algorithm to find all prime numbers up to a certain N. Begin with an (unmarked) array of integers from 2 to N. The first unmarked integer, 2, is the first prime. Mark every multiple of this prime. Repeatedly take the next unmarked integer as the next prime and mark every multiple of the prime.

Note: Invented by Eratosthenes of Cyrene (276 BC - 194 BC).

 For example, here's a beginning array. 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 Since 2 is unmarked, it is our first prime. We mark every second integer, that is, 4, 6, 8, 10, 12, etc. 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 The next unmarked integer is 3, so it is prime. We mark every third integer, i.e., 6, 9, 12, etc. Note that we mark 6, 12, 18, etc. again. 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 Now 5 is the next prime, and we mark every fifth integer. The only new integer marked in range is 25. 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 From here we find the primes 7, 11, 13, 17, 19, and 23.

When we find the prime n, we can begin marking at n². Why? Any composite less than n² is a multiple of a lesser prime, and so will have been marked earlier. As a corollary, we can stop marking when n² is greater than our range. That is, any unmarked numbers greater than the square root of the range are primes.

The naive implementation is not practical for large N since the memory is Θ(N). More efficient implementations use a segmented sieve.

Author: PEB

## Implementation

various implementations (C, Perl, and Java), Peter Luschny's (Java 5 and C#) implementation.