digplanet beta 1: Athena
Share digplanet:

Agriculture

Applied sciences

Arts

Belief

Chronology

Culture

Education

Environment

Geography

Health

History

Humanities

Language

Law

Life

Mathematics

Nature

People

Politics

Science

Society

Technology

Sieve of Eratosthenes: algorithm steps for primes below 121 (including optimization of starting from prime's square).

In mathematics, the sieve of Eratosthenes (Greek: κόσκινον Ἐρατοσθένους), one of a number of prime number sieves, is a simple, ancient algorithm for finding all prime numbers up to any given limit. It does so by iteratively marking as composite (i.e. not prime) the multiples of each prime, starting with the multiples of 2.[1]

The multiples of a given prime are generated starting from that prime, as a sequence of numbers with the same difference, equal to that prime, between consecutive numbers.[1] This is the sieve's key distinction from using trial division to sequentially test each candidate number for divisibility by each prime.[2]

The sieve of Eratosthenes is one of the most efficient ways to find all of the smaller primes (below 10 million or so).[3] It is named after Eratosthenes of Cyrene, a Greek mathematician; although none of his works have survived, the sieve was described and attributed to Eratosthenes in the Introduction to Arithmetic by Nicomachus.[4]

## Algorithm description

Sift the Two's and Sift the Three's,
The Sieve of Eratosthenes.
When the multiples sublime,
The numbers that remain are Prime.

Anonymous[5][6][7]

A prime number is a natural number which has exactly two distinct natural number divisors: 1 and itself.

To find all the prime numbers less than or equal to a given integer n by Eratosthenes' method:

1. Create a list of consecutive integers from 2 to n: (2, 3, 4, ..., n).
2. Initially, let p equal 2, the first prime number.
3. Starting from p, count up in increments of p and mark each of these numbers greater than p itself in the list. These will be multiples of p: 2p, 3p, 4p, etc.; note that some of them may have already been marked.
4. Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise, let p now equal this number (which is the next prime), and repeat from step 3.

When the algorithm terminates, all the numbers in the list that are not marked are prime.

The main idea here is that every value for p is prime, because we have already marked all the multiples of the numbers less than p.

As a refinement, it is sufficient to mark the numbers in step 3 starting from p2, as all the smaller multiples of p will have already been marked at that point. This means that the algorithm is allowed to terminate in step 4 when p2 is greater than n.[1]

Another refinement is to initially list odd numbers only, (3, 5, ..., n), and count up using an increment of 2p in step 3, thus marking only odd multiples of p greater than p itself. This actually appears in the original algorithm.[1] This can be generalized with wheel factorization, forming the initial list only from numbers coprime with the first few primes and not just from odds, i.e. numbers coprime with 2.[8]

### Incremental sieve

An incremental formulation of the sieve[2] generates primes indefinitely (i.e. without an upper bound) by interleaving the generation of primes with the generation of their multiples (so that primes can be found in gaps between the multiples), where the multiples of each prime p are generated directly, by counting up from the square of the prime in increments of p (or 2p for odd primes).

### Trial division

Trial division can be used to produce primes by filtering out the composites found by testing each candidate number for divisibility by its preceding primes. It is often confused with the sieve of Eratosthenes, although the latter directly generates the composites instead of testing for them. Trial division has worse theoretical complexity than that of the sieve of Eratosthenes in generating ranges of primes.[2]

When testing each candidate number, the optimal trial division algorithm uses just those prime numbers not exceeding its square root. The widely known 1975 functional code by David Turner[9] is often presented as an example of the sieve of Eratosthenes[8] but is actually a sub-optimal trial division algorithm.[2]

## Example

To find all the prime numbers less than or equal to 30, proceed as follows.

First generate a list of integers from 2 to 30:

``` 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 28 29 30
```

First number in the list is 2; cross out every 2nd number in the list after it (by counting up in increments of 2), i.e. all the multiples of 2:

``` 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 28 29 30
```

Next number in the list after 2 is 3; cross out every 3rd number in the list after it (by counting up in increments of 3), i.e. all the multiples of 3:

``` 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 28 29 30
```

Next number not yet crossed out in the list after 3 is 5; cross out every 5th number in the list after it (by counting up in increments of 5), i.e. all the multiples of 5:

``` 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 28 29 30
```

Next number not yet crossed out in the list after 5 is 7; the next step would be to cross out every 7th number in the list after it, but they are all already crossed out at this point, as these numbers (14, 21, 28) are also multiples of smaller primes because 7*7 is greater than 30. The numbers left not crossed out in the list at this point are all the prime numbers below 30:

``` 2  3     5     7           11    13          17    19          23                29
```

## Algorithm complexity

Time complexity in the random access machine model is $O(n \log\log n)$ operations, a direct consequence of the fact that the prime harmonic series asymptotically approaches $\log \log n$.

The bit complexity of the algorithm is $O(n (\log n) (\log \log n))$ bit operations with a memory requirement of $O(n)$.[10]

The segmented version of the sieve of Eratosthenes, with basic optimizations, uses $O(n)$ operations and $O(n^{1/2}\log\log n/\log n)$ bits of memory.[11]

## Implementation

```Input: an integer n > 1

Let A be an array of Boolean values, indexed by integers 2 to n,
initially all set to true.

for i = 2, 3, 4, ..., √n :
if A[i] is true:
for j = i2, i2+i, i2+2i, ..., n:
A[j] := false

Now all i such that A[i] is true are prime.
```

Large ranges may not fit entirely in memory. In these cases it is necessary to use a segmented sieve where only portions of the range are sieved at a time.[14]

For ranges with upper limit n so large that the sieving primes below n, as required by the sieve of Eratosthenes, cannot fit in memory, a slower but much more space-efficient sieve like that of Sorenson can be used instead.[15]

## Arithmetic progressions

The sieve may be used to find primes in arithmetic progressions.[16]

## Euler's Sieve

Euler's proof of the zeta product formula contains a version of the sieve of Eratosthenes in which each composite number is eliminated exactly once.[citation needed] It, too, starts with a list of numbers from 2 to n in order. On each step the first element is identified as the next prime and the results of multiplying this prime with each element of the list are marked in the list for subsequent deletion. The initial element and the marked elements are then removed from the working sequence, and the process is repeated:

```[2] (3) 5  7  9  11  13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79  ...
[3]    (5) 7     11  13    17 19    23 25    29 31    35 37    41 43    47 49    53 55    59 61    65 67    71 73    77 79  ...
[4]       (7)    11  13    17 19    23       29 31       37    41 43    47 49    53       59 61       67    71 73    77 79  ...
[5]             (11) 13    17 19    23       29 31       37    41 43    47       53       59 61       67    71 73       79  ...
[...]
```

Here the example is shown starting from odds, after the first step of the algorithm. Thus on kth step all the remaining multiples of the kth prime are removed from the list, which will thereafter contain only numbers coprime with the first k primes (cf. wheel factorization), so that the list will start with the next prime, and all the numbers in it below the square of its first element will be prime too.

Thus when generating a bounded sequence of primes, when the next identified prime exceeds the square root of the upper limit, all the remaining numbers in the list are prime. In the example given above that is achieved on identifying 11 as next prime, giving a list of all primes less than or equal to 80.

Note that numbers that will be discarded by some step are still used while marking the multiples, e.g. for the multiples of 3 it is 3 · 3 = 9, 3 · 5 = 15, 3 · 7 = 21, 3 · 9 = 27, ..., 3 · 15 = 45, ... .

## References

1. ^ a b c d Horsley, Rev. Samuel, F. R. S., "Κόσκινον Ερατοσθένους or, The Sieve of Eratosthenes. Being an account of his method of finding all the Prime Numbers," Philosophical Transactions (1683–1775), Vol. 62. (1772), pp. 327–347.
2. ^ a b c d O'Neill, Melissa E., "The Genuine Sieve of Eratosthenes", Journal of Functional Programming, Published online by Cambridge University Press 9 October 2008 doi:10.1017/S0956796808007004, pp. 10, 11 (contains two incremental sieves in Haskell: a priority-queue–based one by O'Neill and a list–based, by Richard Bird).
3. ^ The Prime Glossary: "The Sieve of Eratosthenes", http://primes.utm.edu/glossary/page.php?sort=SieveOfEratosthenes, references 16. November 2008.
4. ^ Nicomachus, Introduction to Arithmetic, I, 13. [1]
5. ^ Clocksin, William F., Christopher S. Mellish, Programming in Prolog, 1981, p. 174. ISBN 3-540-11046-1.
6. ^ Merritt, Doug (December 14, 2008). "Sieve Of Eratosthenes". Retrieved 2009-03-26.
7. ^ Nykänen, Matti (October 26, 2007). "An Introduction to Functional Programming with the Programming Language Haskell". Retrieved 2009-03-26.
8. ^ a b Colin Runciman, "FUNCTIONAL PEARL: Lazy wheel sieves and spirals of primes", Journal of Functional Programming, Volume 7 Issue 2, March 1997; also here.
9. ^ Turner, David A. SASL language manual. Tech. rept. CS/75/1. Department of Computational Science, University of St. Andrews 1975. (`sieve (p:xs) = p : sieve [x | x <- xs, rem x p > 0]; primes = sieve [2..]`)
10. ^ Pritchard, Paul, "Linear prime-number sieves: a family tree," Sci. Comput. Programming 9:1 (1987), pp. 17–35.
11. ^ A. O. L. Atkin and D. J. Bernstein, "Prime sieves using binary quadratic forms", Mathematics of Computation 73 (2004), pp. 1023–1030.
12. ^ Sedgewick, Robert (1992). Algorithms in C++. Addison-Wesley. ISBN 0-201-51059-6. , p. 16.
13. ^ Jonathan Sorenson, An Introduction to Prime Number Sieves, Computer Sciences Technical Report #909, Department of Computer Sciences University of Wisconsin-Madison, January 2 1990 (the use of optimization of starting from squares, and thus using only the numbers whose square is below the upper limit, is shown).
14. ^ Crandall & Pomerance, Prime Numbers: A Computational Perspective, second edition, Springer: 2005, pp. 121–24.
15. ^ J. Sorenson, The pseudosquares prime sieve, Proceedings of the 7th International Symposium on Algorithmic Number Theory. (ANTS-VII, 2006).
16. ^ J. C. Morehead, "Extension of the Sieve of Eratosthenes to arithmetical progressions and applications", Annals of Mathematics, Second Series 10:2 (1909), pp. 88–104.
 2165 videos foundNext >
 Prime Numbers - Sieve of EratosthenesThe Sieve of Eratosthenes is a simple, ancient algorithm for finding all prime numbers up to a specified integer. In this case we are using a 100's chart. Prime Numbers - The Sieve of EratosthenesFinding all the prime numbers between 1 and 100 using the technique devised by the ancient Greek mathematician Eratosthenes. Sieve of EratosthenesA breakdown of how to use the patterns of Eratosthenes sieve. Basic Math: Sieve of EratosthenesThis lesson consists of showing you how to use the Sieve of Eratosthenes to find all prime numbers below a certain value. In this case, below 100. Sieve of Eratosthenes explained with Math in Color (Prime Numbers, Factors, Multiples)http://mathincolor.com The Sieve of Eratosthenes explained with Math in Color. Prime numbers, multiplication, multiples, factors... The Sieve of Eratosthenes.wmvMade to demonstrate using the Sieve of Eratosthenes to find prime numbers. Middle School. Finding Prime numbers - Sieve of EratosthenesSee complete series on maths problems here: http://www.youtube.com/playlist?list=PL2_aWCzGMAwLL-mEB4ef20f3iqWMGWa25 Sieve of Eratosthenes is a very famous an... Sieve of EratosthenesSieve of Eratosthenes to find prime numbers. Also twin primes and sexy primes. Sieve of Eratosthenes New Animation Sieve of Eratosthenes
 2165 videos foundNext >
 2 news items
 Scientific Computing Unheralded Mathematician Bridges the Prime Gap Scientific Computing Tue, 21 May 2013 08:53:50 -0700 To use the Sieve of Eratosthenes to find, say, all the primes up to 100, start with the number two, and cross out any higher number on the list that is divisible by two. Next move on to three, and cross out all the numbers divisible by three. Four is ... What is a Prime Number? LiveScience.com Mon, 20 May 2013 15:24:50 -0700 In 200 B.C., Eratosthenes created an algorithm that calculated prime numbers, known as the Sieve of Eratosthenes. This algorithm is one of the earliest algorithms ever written. Eratosthenes put numbers in a grid, and then crossed out all multiples of ...
 Limit to books that you can completely read online Include partial books (book previews) .gsc-branding { display:block; }

Oops, we seem to be having trouble contacting Twitter

# Talk About Sieve of Eratosthenes

You can talk about Sieve of Eratosthenes with people all over the world in our discussions.