Sieve of Eratosthenes

The Sieve of Eratosthenes is an algorithm for determining a list or table of all primes less than or equal to a predetermined number. It is named after the Greek mathematician Eratosthenes of Cyrene. However, Eratosthenes, who lived in the 3rd century BC, has not discovered the process, but only the name " sieve " for a long time introduced methods known before his time.

Operation

First, all numbers 2, 3, 4, ... written up to an arbitrary maximum value S. The first unmarked numbers are primes potential. The smallest unmarked number is always a prime number. After a prime number was found, all multiples of this prime number to be marked as composed. Determine the next larger number unmarked. Since it is not a multiple of numbers smaller than themselves (otherwise they would have been marked), it can only by one and itself be divisible. Consequently, it must be a prime number. This is accordingly issued as prime. It deletes all multiples again and leads the process continues until you reach the end of the list. During the procedure, all prime numbers are issued.

Since a prime factor of a composite number is always less than or equal to the square root of the number must be, it is sufficient to remove only the multiples of numbers that are less than or equal to the square root of the barrier south.

Likewise, it is sufficient with a swipe of the multiples to start with the square of a prime number, since all smaller multiples are already marked.

Thus, the process begins to rule out the multiples of 4, 6, 8, ... the smallest prime number 2. The next unmarked number is the next largest prime number 3 Then their multiples 9, 12, 15, ... strikeout, and so on.

Demonstration

Methods, such as the prime numbers between 2 and 120 are determined: First all multiples of 2 are deleted, then all multiples of 3, 5, and 7 marks each begin with the square of the prime number: 4, 9, 25, 49 Since already 112 = 121 is no longer in range, any composite longer be selected from 11; all still unmarked numbers are prime.

Implementation

An exemplary implementation of the algorithm as a pseudo-code:

Const N = 10000   var removed: array of boolean [ N 2. ]     / / Initialization of the prime field   / / All the figures in the field are not painted at the beginning   for i = 2 to N do       deleted [i ] = false   end     / Pay / screens with all the ( prime) i   / / Where i is the smallest prime factor of a composite number j = i * k.   / / The smallest prime factor of a complex number j can not be greater than the root of j <= n.   for i = 2 to sqrt ( N) do       if not deleted [i ] then           / / I is prime, i give out           print i; ",";           / / And underline its multiples, starting with i * i           / / (For k * i with k < i was canceled even as a multiple of k )           for j = i * i to N step i do               deleted [j ] = true           end       end if   end   / / Give the prime numbers greater than root n from. Thus, those have not yet been deleted   for i = sqrt ( N) 1 to N do       if not deleted [i ] then           / / I is prime, i give out           print i; ",";       end if   end Optimized process: only the previously selected multiple of a prime number marked The process can be optimized if only the odd numbers are stored in it. Generally it can be a ( small ) product of ( Prim ) pay the possible primes determine. Sieving must then be applied only to a multiple of these numbers. In the example, each line consists of 10 = 2 * 5 entries. It can be seen that the multiples of 2,4,5,6,8,10 not need to be considered in the lines below, as it does not come as multiples of 2 and 5 as prime numbers in questions. These multiples are visible as horizontal lines. While there are better methods than the sieve of Eratosthenes (eg the sieve of Atkin ), but is still optimal when larger number regions are to be searched for the primes mentioned here.