Sieve of Eratosthenes

from Wikipedia, the free encyclopedia

The sieve of Eratosthenes is an algorithm for determining a list or table of all prime numbers less than or equal to a given number. It is named after the Greek mathematician Eratosthenes . However, Eratosthenes, who in the 3rd century BC BC, the process was not discovered, but only the name "sieve" was introduced for the process, which was known long before its time.

functionality

Basic procedure: All multiples of a prime number that are greater than or equal to its square are marked.

First all numbers 2, 3, 4, ... up to a freely selectable maximum value S are written down. The initially unmarked numbers are potential prime numbers. The smallest unmarked number is always a prime number. After a prime has been found, all multiples of that prime are marked as composite . Determine the next larger unmarked number. Since it is not a multiple of numbers smaller than itself (otherwise it would have been marked), it can only be divisible by one and itself. Hence it must be a prime number. Accordingly, this is output as a prime number. You delete all multiples again and continue the process until you reach the end of the list. In the course of the process, all prime numbers are output.

Since at least one prime factor of a composite number must always be less than or equal to the square root of the number, it is sufficient to delete only the multiples of numbers that are less than or equal to the square root of the bound S.

Likewise, when crossing out the multiple, it is sufficient to start with the square of the prime number, since all smaller multiples are already marked.

The procedure starts with crossing out the multiple 4, 6, 8, ... of the smallest prime number 2. The next unmarked number is the next higher prime number, the 3. Then its multiple 9, 12, 15, ... are crossed out, and so on.

demonstration

Procedure for determining the prime numbers between 2 and 120: First all multiples of 2 are deleted, then all multiples of 3, 5, and 7. The markings each begin with the square of the prime number: 4, 9, 25, 49. Da 11 2 = 121 is already no longer in the range of values, from 11 onwards no more composite numbers are marked; all unmarked numbers are prime.

implementation

An exemplary implementation of the algorithm as pseudocode : 

 const N = 10000
 var gestrichen: array [2..N] of boolean

 // Initialisierung des Primzahlfeldes
 // Alle Zahlen im Feld sind zu Beginn nicht gestrichen
 for i = 2 to N do
     gestrichen[i] = false
 end

 // Siebe mit allen (Prim-) Zahlen i, wobei i der kleinste Primfaktor einer zusammengesetzten
 // Zahl j = i*k ist. Der kleinste Primfaktor einer zusammengesetzten Zahl j kann nicht größer
 // als die Wurzel von j <= n sein.
 for i = 2 to sqrt(N) do
     if not gestrichen[i] then
         // i ist prim, gib i aus...
         print i; ", ";
         // ...und streiche seine Vielfachen, beginnend mit i*i
         // (denn k*i mit k<i wurde schon als Vielfaches von k gestrichen)
         for j = i*i to N step i do
             gestrichen[j] = true
         end
     end if
 end
 // Gib die Primzahlen größer als Wurzel(n) aus - also die, die noch nicht gestrichen wurden
 for i = sqrt(N)+1 to N do
     if not gestrichen[i] then
         // i ist prim, gib i aus
         print i; ", ";
     end if
 end
Optimized procedure: only the previously unmarked multiples of a prime number are marked

The process can be optimized if only the odd numbers are stored in it. In general, one can determine the possible prime numbers for a (small) product of (prim) numbers. The seven then only has to be applied to the 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 in the lines below do not have to be considered, since as multiples of 2 or 5 they do not come into question as prime numbers. These multiples can be seen as vertical lines. There are more efficient processes than the sieve of Eratosthenes (e.g. the sieve of Atkin ).

literature

Web links

Wikibooks: source code of the algorithm in various programming languages  - learning and teaching materials