◀ ▲ ▶Branches / Number-theory / Sieve-methods / Definition: Sieve of Eratosthenes

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:

Mentioned in:

Lemmas: 1

Thank you to the contributors under CC BY-SA 4.0!

Github:

References

Bibliography

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