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.

1. 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. 1 nie jest liczbą pierwszą, więc ją skreślamy.

       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

3. Listę rozpoczyna liczba 2. Jest to liczba pierwsza. Teraz wykreślamy wszystkie liczby większe od 2 i podzielne przez 2.

   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

4. 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

5. 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

6. 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 p² - 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

   

1. 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.

1. Jeden nie jest liczbą pierwszą, więc wyjdzie z koła

2. Wyjdą z koła uczniowie, którzy mają liczby podzielne przez 2 (oprócz 2).

3. Następnie wyjdą ci uczniowie, którzy mają liczby podzielne przez 3 (oprócz 3).

4. 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.

2. 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ć p², 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 S_i = 1, jeśli 2i + 1 jest liczbą pierwszą, a 0 - w przeciwnym przypadku.

Krok 1 {Początkowe wartości zmiennych} S_j : = 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 S_j : = 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

1. Znajdź wszystkie liczby pierwsze metodą sita Eratostenesa z przedziału liczb naturalnych od 1 do 200.

2. 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

---