Generowanie kolejnych liczb pierwszych - sito Eratostenesa
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:
1 |
2 |
3 |
|
5 |
|
7 |
|
9 |
|
11 |
|
13 |
|
15 |
|
17 |
|
19 |
|
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:
1 |
2 |
3 |
|
5 |
|
7 |
|
|
|
11 |
|
13 |
|
|
|
17 |
|
19 |
|
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:
|
2 |
3 |
|
5 |
|
7 |
|
|
|
11 |
|
13 |
|
|
|
17 |
|
19 |
|
W sicie, Eratostenesa może pojawić się jeden problem - a mianowicie, do której liczby mamy dojść idąc od lewej od liczby 2, aby w danym przedziale zostały nam tylko liczby pierwsze? Moja odpowiedź brzmi do zaokrąglonego w dół pierwiastka kwadratowego największej liczby z danego przedziału. W naszym przypadku największą liczbą jest 20. Pierwiastek kwadratowy z 20 to około 4,47. Gdy zaokrąglimy tą liczbę w dół to otrzymamy 4. I tylko do tej liczby doszedłem w przykładzie powyżej. Teraz postaram się wytłumaczyć, dlaczego akurat dochodzimy do tej liczby. Każda liczba złożona w danym przedziale to iloczyn dwóch innych liczb (nie muszą być one koniecznie pierwsze). Liczby te mogą być równe sobie - wtedy wartość tych liczb to pierwiastek kwadratowy z danej liczby złożonej. Jednakże, gdy liczby te nie są sobie równe - to jedna jest większa, a druga mniejsza. Mniejsza z tych liczb jest mniejsza od pierwiastka kwadratowego z danej liczby złożonej. Tak, więc, aby skreślić daną liczbę złożoną musimy dojść, (gdy idziemy po kolei od 2) do tej mniejszej liczby, nie musimy wcale dochodzić do tej większej.
Kartka 2
Przypuśćmy, że chcemy znaleźć wszystkie liczby pierwsze wśród liczb od 1 do 100.
Ustawiamy liczby w ciąg:
1 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
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100
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
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100
2 3 5 7 9
11 13 15 17 19
21 23 25 27 29
31 33 35 37 39
41 43 45 47 49
51 53 55 57 59
61 63 65 67 69
71 73 75 77 79
81 83 85 87 89
91 93 95 97 99
Najmniejszą liczbą jest teraz liczba 3 (jest to liczba pierwsza - gdyby nią nie była, to dzieliłaby się, przez 2, ale wtedy byłaby wykreślona). Skreślamy teraz z listy wszystkie liczby większe od 3 i podzielne przez 3.
2 3 5 7
11 13 17 19
23 29
31 35 37
41 43 47 49
53 55 59
61 65 67
71 73 77 79
83 85 89
91 95 97
Najmniejszą liczbą na liście jest liczba 5. Jest to liczba pierwsza (argumentacja jak wyżej). Skreślamy teraz wszystkie liczby podzielne przez 5 i większe od 5.
2 3 5 7
11 13 17 19
23 29
31 37
41 43 47 49
53 59
61 67
71 73 77 79
83 89
91 97
Najmniejszą liczbą na liście jest liczba 7. Jest ona liczbą pierwszą. Wykreślamy wszystkie jej wielokrotności.
2 3 5 7
11 13 17 19
23 29
31 37
41 43 47
53 59
61 67
71 73 79
83 89
97
Zwróćmy uwagę, że do znalezienia wszystkich liczb pierwszych wystarczy badać liczby pierwsze niewiększe od
. Dzieje się tak, dlatego, że biorąc pod uwagę liczbę pierwszą p, zaczynam skreślanie od liczby p2 - mniejsze wielokrotności p są już skreślone (dzielą się przez liczbę mniejszą od p).
Najbliższą liczbą pierwszą jest 11. Zauważmy, że
, więc znaleźliśmy wszystkie liczby pierwsze od 1 do 100.
Oto one:
2 3 5 7
11 13 17 19
23 29
31 37
41 43 47
53 59
61 67
71 73 79
83 89
97
Na czym polega generowanie kolejnych liczb pierwszych w sicie Eratostenesa?
Co to jest algorytm?
Algorytm jest dokładnym przepisem rozwiązania problemu lub osiągnięcia zamierzonego celu krok po kroku. Osiągnięcie założonego przez nas celu zależeć będzie również od zaproponowanego sposobu rozwiązywania, a dokładniej - techniki algorytmicznej. Jedną z form przedstawienia algorytmu, dla jego przejrzystości służy tzw. algorytm blokowy
algorytm blokowy:
opis krok po kroku rozwiązania postawionego problemu lub sposobu osiągnięcia jakiegoś celu, który powinien być dokładnie określony w postaci umownych bloków decyzyjnych.
Cechy algorytmu:
dane winny być dokładnie sprecyzowane ( winny być uniwersalne),
cel (wynik), który chcemy osiągnąć jasno określony oraz powiązany z danymi; to powiązanie danych z wynikiem - czyli jak rodzaj i ilość oraz jakość danych wpłynie na wynik, ( nazywamy to specyfikacją problemu).
W celu lepszego zrozumienia idei algorytmu, zaproponowano zabawę z uczniami w oparciu o przedstawiony schemat algorytmu. Dopiero po przeprowadzonej zabawie i dyskusji, można przystąpić do rysowania schematu blokowego algorytmu oraz do sprawdzenie jego działania na innych przykładach.
Na tablicy wisi plansza złożona ze stu pierwszych liczb naturalnych:
1 |
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 |
31 |
32 |
33 |
34 |
35 |
36 |
37 |
38 |
39 |
40 |
41 |
42 |
43 |
44 |
45 |
46 |
47 |
48 |
49 |
50 |
51 |
52 |
53 |
54 |
55 |
56 |
57 |
58 |
59 |
60 |
61 |
62 |
63 |
64 |
65 |
66 |
67 |
68 |
69 |
70 |
71 |
72 |
73 |
74 |
75 |
76 |
77 |
78 |
79 |
80 |
81 |
82 |
83 |
84 |
85 |
86 |
87 |
88 |
89 |
90 |
91 |
92 |
93 |
94 |
95 |
96 |
97 |
98 |
99 |
100 |
Uczniowie podchodzą do tablicy i skreślają liczby złożone według podanego algorytmy Eratostenesa.
Następnie uczniowie przeprowadzają zabawę ruchową. Proponujemy, aby uczniowie ustawili się na środku klasy w półkole.
Każdy uczeń dostaje kartkę z liczbą (od 1 do 30). Zgodnie z algorytmem sita Eratostenesa „przesiewają” liczby, które trzymają uczniowie.
Jeden nie jest liczbą pierwszą, więc wyjdzie z koła
Wyjdą z koła uczniowie, którzy mają liczby podzielne przez 2 (oprócz 2).
Następnie wyjdą ci uczniowie, którzy mają liczby podzielne przez 3 (oprócz 3).
Następnie wyjdą z koła liczby podzielne przez 5 (oprócz 5).
Jakie liczby zostały w kole, czyli w sicie? ( rysunek 2).
W działaniu sita Eratostenesa widoczny jest analogia do sit stosowanych w praktyce np. wialnia - maszyna do oczyszczania ziarna z plew składa się z kilku sit o różnej gęstości siatki drucianej. Również liczby z przedziału (2,30) przechodzą przez trzy sita zatrzymując odpowiednie wielokrotności 2, 3 i 5.
Liczby pierwsze są tymi, które nie przeszły przez zestaw sit.
Algorytm - sito Eratostenesa
Przyjmujemy spostrzeżenia:
Wystarczy od samego początku rozważać jedynie liczby nieparzyste, gdyż parzyste będą „przesiane” w pierwszym kroku przez oczka nastawiona na liczby podzielne przez 2;
Niech p będzie kolejną liczbą pierwszą, której mamy użyć do odsiania liczb złożonych, podzielnych przez p. wtedy wystarczy wyeliminować liczby mające postać p2, p(p+2), p(p+4),... Wynika stąd, że liczby q p, gdzie q < p, zostały przesiane przez q, a liczb p(p+1), p(p+3),.... nie musimy już przesiewać, gdyż są one parzyste (p, jako liczba pierwsza, jest liczbą nieparzystą).
Kolejnym uproszczeniem jest wykonanie w algorytmie jedynie dodawań w miejsce mnożeń - kolejno eliminowana liczba jest, bowiem o 2p większa od poprzedniej.
Algorytm sita Eratostenesa
Dane: Liczba naturalna N (dla uproszczenia można założyć, że jest to liczba parzysta równa 2M).
Wyniki: Tablica S[1..M], w której Si = 1, jeśli 2i + 1 jest liczbą pierwszą, a 0 - w przeciwnym przypadku.
Krok 1 {Początkowe wartości zmiennych} Sj : = 1 dla j = 1, 2, ...,M; i : =1; p : = 3, q : = 4.
Krok 2 Jeśli Si = 0, to przejdź do kroku 4.
Krok 3 {Liczba pierwsza p służy do odsiania jej wielokrotności, począwszy od miejsca q w tablicy S}
Przyjmij j : = q. Dopóki j ≤ M, wykonuj Sj : = 0; j : = j + p.
Krok 4 Wykonaj przypisania: i : = i + 1; p : = p + 2; q : = q + 2p - 2. Jeśli q ≤ M, to wróć do kroku 2, a w przeciwnym razie zakończ algorytm.
Przykład działania sita Eratostenesa dla liczby naturalnej N = 100 |
||||
i |
S[i] |
p |
q |
Odsiane liczby |
1 |
1 |
3 |
4 |
9, 15, 21, 27, 33, 39, 45, 51, 57, 63, 69, 75, 81, 87, 93, 99 |
2 |
1 |
5 |
12 |
25, 35, 45, 55, 65, 75, 85, 95 |
3 |
1 |
7 |
24 |
49, 63, 77, 91 |
4 |
0 |
9 |
40 |
p nie jest liczbą pierwszą |
5 |
1 |
11 |
60 |
q > M - koniec algorytmu |
Sposób przedstawiania uczniom algorytmu
Zadanie domowe
Znajdź wszystkie liczby pierwsze metodą sita Eratostenesa z przedziału liczb naturalnych od 1 do 200.
Przetestuj działanie algorytmu Eratostenesa w przedziale od 1 do 500 (dla zainteresowanych).
5.Osiągnięcia ucznia
Uczeń:
potrafi współpracować w grupie i podejmować decyzje przy realizacji wspólnego zadania,
potrafi przekazywać swoje pomysły i informacje w różnych formach, używając tekstu, rysunku,
potrafi prowadzić obserwacje i posługiwać się modelami przy objaśnianiu zagadnień i problemów,
potrafi samodzielnie zapisywać proste algorytmy w postaci procedur,
zna proste sposoby i przykłady testowania zaproponowanych rozwiązań,
potrafi zaproponować rozwiązania alternatywne,
zaproponowane rozwiązania potrafi przetwarzać, modyfikować wykorzystywać w innych zadaniach,
posiada umiejętność dyskutowania i wprowadzania zmian.
Podaj zakres liczb pierwszych M
j : = 1 p : = 3
i : = 1 q : = 4
1 → <j> <0>
j = M
j : = j + 1
<j> <0> → S
S : = 0
j : = q
j > M
0 → <j> <0>
j : = j + p
i : = i + 1
p : = p + 2
q : = q +2p - 2
q ≤ M
Koniec
Start
N
N
N
N