Das Sieb des Eratosthenes

Wie findest du alle Primzahlen bis 100, ohne jede Zahl einzeln zu testen? Mit einem über 2.000 Jahre alten Verfahren: Du streichst alle Vielfachen aus, und die Primzahlen bleiben im „Sieb“ hängen. Es ist nach Eratosthenes von Kyrene benannt, der im 3. Jahrhundert v. Chr. in Alexandria lebte, einem Zentrum der hellenistischen Mathematik.

1. Schreibe die Zahlen von 1 bis 100 in ein Gitter und streiche die 1.
2. Die 2 bleibt stehen, alle ihre Vielfachen (4, 6, 8, …) streichst du.
3. Die nächste freie Zahl ist die 3. Sie bleibt, ihre Vielfachen (6, 9, 12, …) streichst du.
4. Mache mit 5 und 7 genauso. Dann bist du fertig, denn schon 11 · 11 = 121 liegt über 100.

Alle Zahlen, die übrig bleiben, sind prim. Es sind genau 25.