Mo logo [home] [lexicon] [problems] [tests] [courses] [auxiliaries] [notes] [staff] german flag
Mathematik-Online lexicon:

The Sieve of Eratosthenes

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z overview
The sieve of Eratosthenes can be used to generate a list of primes.

Starting with a sequence of already known primes, for example the first four primes

$\displaystyle 2,3,5,7 \,, $

we cross out all multiples of these primes from the sequence of subsequent integers. In our example we obtain the sequence

$\displaystyle 11,\,13,\,17,\,19,\,23,\,29,\,31,\,37,\, 41,\,43,\,47,\,\ldots \,. $

All numbers $ \le 7^2$ in this sequence are prime, since

$\displaystyle p q = n \le 7^2 = 49 $

implies that at least one of the factors $ p$ or $ q$ has to be $ \le 7$. Therefore, the integer $ n$ must have a prime factor $ \le 7$, yet all those integers have already been crossed out.

The procedure can be repeated. By deleting all multiples of primes $ p$ with $ p \le 47$, we obtain in the next step all prime numbers $ <47^2 = 2209$.

(Authors: Höllig/Abele)
[Links]
  automatisch erstellt am 29.  4. 2011