Przykład 1.
Sformułuj specyfikację problemu szukania liczb pierwszych w zbiorze od 1 do 20. Przykład do omówienia (kartka 1).
Przykład 2.
Sformułuj specyfikację problemu szukania liczb pierwszych w zbiorze od 1 do 100. Przykład do omówienia (kartka 2).
Kartka 1
Znajdźmy na przykład wszystkie liczby pierwsze od 1 do 20. Liczby złożone będą po kolei "usuwane" w sposób podany niżej. Na początku nasz przedział wygląda następująco:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Cała idea tego algorytmu polega na tym, że "idziemy" od lewej strony przedziału poczynając od liczby 2 i gdy liczba ta nie została wcześniej skreślona to skreślamy wszystkie jej wielokrotności w danym przedziale oprócz niej samej.
Tak więc zaczynamy od liczby 2. Nie jest ona skreślona, więc skreślamy jej wielokrotności oprócz niej samej. W tym przypadku są to liczby: 4, 6, 8, 10, 12, 14, 16, 18, 20.
Po skreśleniu (usunięciu) wyżej wymienionych liczb otrzymujemy:
Kolejną liczbę, jaką napotykamy po 2 jest liczba 3. Nie została ona wcześniej skreślona, więc skreślamy wszystkie jej wielokrotności w naszym przedziale od 1 do 20 oprócz niej samej. Proszę zauważyć, iż niektóre wielokrotności liczby 3 zostały już skreślone wcześniej. Liczby, które w tym przypadku skreślimy to: 6, 9, 12, 15, 18. Po tej operacji otrzymamy:
Kolejną liczbę, jaką napotkamy idąc od lewej to 4. Ponieważ została ona już wcześniej skreślona to nie wykonujemy już żadnych dodatkowych skreśleń.
Proszę zauważyć, że w naszym przedziale zostały już tylko liczby pierwsze. Musimy jeszcze skreślić liczbę 1:
...
Dariu55