Około roku 200 p.n.e grecki matematyk Eratostenes podał algorytm na znajdowanie liczb pierwszych. Nazwa pochodzi od sposobu w jaki są one znajdowane. Wszystkie liczby po kolei przesiewa się - usuwane są spośród nich wszystkie wielokrotności danej liczby.


Odnajdziemy za pomocą sita Eratostenesa wszystkie liczby pierwsze z zakresu od 2 do 30.
Zapisujemy kolejno wszystkie liczby w tabeli.

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

Teraz bierzemy pierwszą liczbę z tabeli (2) i począwszy od następnej wykreślamy z niej wszystkie te liczby, które są przez nią podzielne.

2

3

5

7

9

11

13

15

17

19

21

23

25

27

29

Bierzemy kolejną liczbę (3) i począwszy od następnej wykreślamy z tabeli podzielne przez nią.

2

3

5

7

11

13

17

19

23

25

29

Kolejną liczbą w tabeli jest 5. Postępujemy jak poprzednio.

2

3

5

7

11

13

17

19

23

29

W tym momencie możemy zakończyć nasze poszukiwania. Algorytm "mówi", że kolejne wykreślania należy powtarzać, nie dalej jak do liczby będącej zaokrąglonym w dół pierwiastkiem zakresu. U nas jest to: po zaokrągleniu w dół otrzymujemy 5. W tabeli zostały już tylko liczby pierwsze.