# Definition: Sieve of Eratosthenes

It is well-known that there are infinitely many prime numbers. Due to Eratosthenes of Cyrene, the following efficient method, called the sieve of Eratosthenes, can be used to find prime numbers:

1. Start with the sequence of numbers $$2,3,4,\ldots$$.
2. The first number, which is not "sieved", is $$2$$. This is the first prime number.
3. Remove from the sequence all proper multiples of $$2$$, i.e. the numbers $$2k$$ for $$k=2,3,4,\ldots$$.
4. Look for the next number, which is not "sieved"; this is $$3$$. This is the next prime number.
5. Remove from the sequence all proper multiples of $$3$$, i.e. the numbers $$3k$$ for $$k=2,3,4,\ldots$$.
6. Repeat this procedure for any next number, which hes not yet been "sieved".
7. This procedure leads to the sequence of prime numbers, i.e. $$2,3,5,7,11,\ldots$$.

The following figure visualizes the sieve of Eratosthenes: Lemmas: 1

Github: ### References

#### Bibliography

1. Scheid Harald: "Zahlentheorie", Spektrum Akademischer Verlag, 2003, 3rd Edition