Sieve Of Eratosthenes
   HOME

TheInfoList



OR:

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, the sieve of Eratosthenes is an ancient
algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
for finding all
prime number A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
s up to any given limit. It does so by iteratively marking as
composite Composite or compositing may refer to: Materials * Composite material, a material that is made from several different substances ** Metal matrix composite, composed of metal and other parts ** Cermet, a composite of ceramic and metallic materials ...
(i.e., not prime) the multiples of each prime, starting with the first prime number, 2. The multiples of a given prime are generated as a sequence of numbers starting from that prime, with constant difference between them that is equal to that prime.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
This is the sieve's key distinction from using
trial division Trial division is the most laborious but easiest to understand of the integer factorization algorithms. The essential idea behind trial division tests to see if an integer ''n'', the integer to be factored, can be divided by each number in turn t ...
to sequentially test each candidate number for divisibility by each prime. Once all the multiples of each discovered prime have been marked as composites, the remaining unmarked numbers are primes. The earliest known reference to the sieve ( grc, κόσκινον Ἐρατοσθένους, ''kóskinon Eratosthénous'') is in
Nicomachus of Gerasa Nicomachus of Gerasa ( grc-gre, Νικόμαχος; c. 60 – c. 120 AD) was an important ancient mathematician and music theorist, best known for his works ''Introduction to Arithmetic'' and ''Manual of Harmonics'' in Greek. He was born in ...
's ''
Introduction to Arithmetic The book ''Introduction to Arithmetic'' ( grc-gre, Ἀριθμητικὴ εἰσαγωγή, ''Arithmetike eisagoge'') is the only extant work on mathematics by Nicomachus (60–120 AD). Summary The work contains both philosophical prose an ...
'', an early 2nd cent. CE book which attributes it to
Eratosthenes of Cyrene Eratosthenes of Cyrene (; grc-gre, Ἐρατοσθένης ;  – ) was a Greek polymath: a mathematician, geographer, poet, astronomer, and music theorist. He was a man of learning, becoming the chief librarian at the Library of Alexandria ...
, a 3rd cent. BCE Greek mathematician, though describing the sieving by odd numbers instead of by primes. One of a number of prime number sieves, it is one of the most efficient ways to find all of the smaller primes. It may be used to find primes in
arithmetic progression An arithmetic progression or arithmetic sequence () is a sequence of numbers such that the difference between the consecutive terms is constant. For instance, the sequence 5, 7, 9, 11, 13, 15, . . . is an arithmetic progression with a common differ ...
s.


Overview

A
prime number A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
is a
natural number In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called ''Cardinal n ...
that has exactly two distinct natural number
divisor In mathematics, a divisor of an integer n, also called a factor of n, is an integer m that may be multiplied by some integer to produce n. In this case, one also says that n is a multiple of m. An integer n is divisible or evenly divisible by ...
s: the number 1 and itself. To find all the prime numbers less than or equal to a given integer by Eratosthenes' method: # Create a list of consecutive integers from 2 through : . # Initially, let equal 2, the smallest prime number. # Enumerate the multiples of by counting in increments of from to , and mark them in the list (these will be ; the itself should not be marked). # Find the smallest number in the list greater than that is not marked. If there was no such number, stop. Otherwise, let now equal this new number (which is the next prime), and repeat from step 3. # When the algorithm terminates, the numbers remaining not marked in the list are all the primes below . The main idea here is that every value given to will be prime, because if it were composite it would be marked as a multiple of some other, smaller prime. Note that some of the numbers may be marked more than once (e.g., 15 will be marked both for 3 and 5). As a refinement, it is sufficient to mark the numbers in step 3 starting from , as all the smaller multiples of will have already been marked at that point. This means that the algorithm is allowed to terminate in step 4 when is greater than . Another refinement is to initially list odd numbers only, , and count in increments of in step 3, thus marking only odd multiples of . This actually appears in the original algorithm. This can be generalized with
wheel factorization Wheel factorization is an improvement of the trial division method for integer factorization. The trial division method consists of dividing the number to be factorized successively by the first integers (2, 3, 4, 5, ...) until finding a divisor ...
, forming the initial list only from numbers
coprime In mathematics, two integers and are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides does not divide , and vice versa. This is equivale ...
with the first few primes and not just from odds (i.e., numbers coprime with 2), and counting in the correspondingly adjusted increments so that only such multiples of are generated that are coprime with those small primes, in the first place.


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 The first number in the list is 2; cross out every 2nd number in the list after 2 by counting up from 2 in increments of 2 (these will be all the multiples of 2 in the list):  2 3 5 7 9 11 13 15 17 19 21 23 25 27 29 The next number in the list after 2 is 3; cross out every 3rd number in the list after 3 by counting up from 3 in increments of 3 (these will be all the multiples of 3 in the list):  2 3 5 7 11 13 17 19 23 25 29 The next number not yet crossed out in the list after 3 is 5; cross out every 5th number in the list after 5 by counting up from 5 in increments of 5 (i.e. all the multiples of 5):  2 3 5 7 11 13 17 19 23 29 The 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 7, 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 not crossed out at this point in the list are all the prime numbers below 30:  2 3 5 7 11 13 17 19 23 29


Algorithm and variants


Pseudocode

The sieve of Eratosthenes can be expressed in pseudocode, as follows:, p. 16.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).
algorithm Sieve of Eratosthenes is input: an integer ''n'' > 1. output: all prime numbers from 2 through ''n''. let ''A'' be an array of Boolean values, indexed by integers 2 to ''n'', initially all set to true. for ''i'' = 2, 3, 4, ..., not exceeding do if ''A'' 'i''is true for ''j'' = ''i''2, ''i''2+''i'', ''i''2+2''i'', ''i''2+3''i'', ..., not exceeding ''n'' do set ''A'' 'j'':= false return all ''i'' such that ''A'' 'i''is true. This algorithm produces all primes not greater than . It includes a common optimization, which is to start enumerating the multiples of each prime from . The
time complexity In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by t ...
of this algorithm is , provided the array update is an operation, as is usually the case.


Segmented sieve

As Sorenson notes, the problem with the sieve of Eratosthenes is not the number of operations it performs but rather its memory requirements. For large , the range of primes may not fit in memory; worse, even for moderate , its
cache Cache, caching, or caché may refer to: Places United States * Cache, Idaho, an unincorporated community * Cache, Illinois, an unincorporated community * Cache, Oklahoma, a city in Comanche County * Cache, Utah, Cache County, Utah * Cache County ...
use is highly suboptimal. The algorithm walks through the entire array , exhibiting almost no
locality of reference In computer science, locality of reference, also known as the principle of locality, is the tendency of a processor to access the same set of memory locations repetitively over a short period of time. There are two basic types of reference localit ...
. A solution to these problems is offered by ''segmented'' sieves, where only portions of the range are sieved at a time. These have been known since the 1970s, and work as follows: # Divide the range 2 through into segments of some size . # Find the primes in the first (i.e. the lowest) segment, using the regular sieve. # For each of the following segments, in increasing order, with being the segment's topmost value, find the primes in it as follows: ## Set up a Boolean array of size , and ## Mark as non-prime the positions in the array corresponding to the multiples of each prime found so far, by calculating the lowest multiple of between and , and enumerating its multiples in steps of as usual. The remaining positions correspond to the primes in the segment, since the square of a prime in the segment is not in the segment (for , one has (k\Delta + 1)^2 > (k+1)\Delta). If is chosen to be , the space complexity of the algorithm is , while the time complexity is the same as that of the regular sieve. For ranges with upper limit so large that the sieving primes below as required by the page segmented sieve of Eratosthenes cannot fit in memory, a slower but much more space-efficient sieve like the sieve of Sorenson can be used instead.


Incremental sieve

An incremental formulation of the sieveO'Neill, Melissa E.
"The Genuine Sieve of Eratosthenes"
''Journal of Functional Programming'', published online by Cambridge University Press 9 October 2008 , pp. 10, 11 (contains two incremental sieves in Haskell: a priority-queue–based one by O'Neill and a list–based, by Richard Bird).
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 are generated directly by counting up from the square of the prime in increments of (or for odd primes). The generation must be initiated only when the prime's square is reached, to avoid adverse effects on efficiency. It can be expressed symbolically under the dataflow paradigm as ''primes'' = '2'', ''3'', ...\ ''p''², ''p''²+''p'', ...for ''p'' in ''primes''], using
list comprehension A list comprehension is a syntactic construct available in some programming languages for creating a list based on existing lists. It follows the form of the mathematical ''set-builder notation'' (''set comprehension'') as distinct from the use of ...
notation with \ denoting set subtraction of
arithmetic progressions An arithmetic progression or arithmetic sequence () is a sequence of numbers such that the difference between the consecutive terms is constant. For instance, the sequence 5, 7, 9, 11, 13, 15, . . . is an arithmetic progression with a common differ ...
of numbers. Primes can also be produced by iteratively sieving out the composites through divisibility testing by sequential primes, one prime at a time. It is not the sieve of Eratosthenes but is often confused with it, even though the sieve of Eratosthenes 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. When testing each prime, the ''optimal'' trial division algorithm uses all prime numbers not exceeding its square root, whereas the sieve of Eratosthenes produces each composite from its prime factors only, and gets the primes "for free", between the composites. The widely known 1975 functional sieve code by David Turner is often presented as an example of the sieve of Eratosthenes but is actually a sub-optimal trial division sieve.


Algorithmic complexity

The sieve of Eratosthenes is a popular way to benchmark computer performance. The
time complexity In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by t ...
of calculating all primes below in the
random access machine In computer science, random-access machine (RAM) is an abstract machine in the general class of register machines. The RAM is very similar to the counter machine but with the added capability of 'indirect addressing' of its registers. Like the cou ...
model is operations, a direct consequence of the fact that the prime harmonic series asymptotically approaches . It has an exponential time complexity with regard to input size, though, which makes it a pseudo-polynomial algorithm. The basic algorithm requires of memory. The
bit complexity In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) ...
of the algorithm is bit operations with a memory requirement of . The normally implemented page segmented version has the same operational complexity of as the non-segmented version but reduces the space requirements to the very minimal size of the segment page plus the memory required to store the base primes less than the square root of the range used to cull composites from successive page segments of size . A special (rarely, if ever, implemented) segmented version of the sieve of Eratosthenes, with basic optimizations, uses operations and bits of memory.Paul Pritchard, "A sublinear additive sieve for finding prime numbers", ''Communications of the ACM'' 24 (1981), 18–23. Paul Pritchard, Explaining the wheel sieve, Acta Informatica 17 (1982), 477–485. Paul Pritchard, "Fast compact prime number sieves" (among others), ''Journal of Algorithms'' 4 (1983), 332–344. Using big O notation ignores constant factors and offsets that may be very significant for practical ranges: The sieve of Eratosthenes variation known as the Pritchard wheel sieve has an performance, but its basic implementation requires either a "one large array" algorithm which limits its usable range to the amount of available memory else it needs to be page segmented to reduce memory use. When implemented with page segmentation in order to save memory, the basic algorithm still requires about bits of memory (much more than the requirement of the basic page segmented sieve of Eratosthenes using bits of memory). Pritchard's work reduced the memory requirement at the cost of a large constant factor. Although the resulting wheel sieve has performance and an acceptable memory requirement, it is not faster than a reasonably Wheel Factorized basic sieve of Eratosthenes for practical sieving ranges.


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. The same sieve was rediscovered and observed to take linear time by .. It, too, starts with a
list A ''list'' is any set of items in a row. List or lists may also refer to: People * List (surname) Organizations * List College, an undergraduate division of the Jewish Theological Seminary of America * SC Germania List, German rugby union ...
of numbers from 2 to in order. On each step the first element is identified as the next prime, is multiplied with each element of the list (thus starting with itself), and the results 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:
  (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 ...   (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 ...   (7) 11 13 17 19 23 29 31 37 41 43 47 49 53 59 61 67 71 73 77 79 ...   (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 the th step all the remaining multiples of the th prime are removed from the list, which will thereafter contain only numbers coprime with the first primes (cf.
wheel factorization Wheel factorization is an improvement of the trial division method for integer factorization. The trial division method consists of dividing the number to be factorized successively by the first integers (2, 3, 4, 5, ...) until finding a divisor ...
), 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 a step are still used while marking the multiples in that step, e.g., for the multiples of 3 it is , , , , ..., , ..., so care must be taken dealing with this.


See also

* Sieve of Pritchard *
Sieve of Atkin In mathematics, the sieve of Atkin is a modern algorithm for finding all prime numbers up to a specified integer. Compared with the ancient sieve of Eratosthenes, which marks off multiples of primes, the sieve of Atkin does some preliminary work a ...
*
Sieve of Sundaram In mathematics, the sieve of Sundaram is a variant of the sieve of Eratosthenes, a simple deterministic algorithm for finding all the prime numbers up to a specified integer. It was discovered by Indian student S. P. Sundaram in 1934. Algorithm ...
*
Sieve theory Sieve theory is a set of general techniques in number theory, designed to count, or more realistically to estimate the size of, sifted sets of integers. The prototypical example of a sifted set is the set of prime numbers up to some prescribed lim ...


References


External links


primesieve – Very fast highly optimized C/C++ segmented Sieve of Eratosthenes

''Eratosthenes, sieve of'' at Encyclopaedia of Mathematics



Sieve of Eratosthenes
by George Beck,
Wolfram Demonstrations Project The Wolfram Demonstrations Project is an organized, open-source collection of small (or medium-size) interactive programs called Demonstrations, which are meant to visually and interactively represent ideas from a range of fields. It is hos ...
.
Sieve of Eratosthenes in Haskell

Sieve of Eratosthenes algorithm illustrated and explained. Java and C++ implementations.



Fast optimized highly parallel CUDA segmented Sieve of Eratosthenes in C

SieveOfEratosthenesInManyProgrammingLanguages c2 wiki page


Sieve of Eratosthenes in C from 1998 with nice features and algorithmic tricks explained. {{DEFAULTSORT:Sieve Of Eratosthenes Primality tests Articles with example pseudocode Algorithms