- nie każdy prosty algorytm jest optymalny i liczba obliczeń w algorytmie ma istotne znaczenie dla jego realizacji,
- zaprogramowanie w Scratchu sita Eratostenesa.
SITO ERATOSTENESA
Sposób Eratostenesa polega na odsiewaniu całych grup liczb, np. liczb parzystych (z wyjątkiem 2), liczb podzielnych przez 3 (z wyjątkiem 3) itd. Przyjrzyj się, jak to działa.
- Najpierw należy wypisać wszystkie liczby w podanym zakresie, np. od 1 do 100.
- Potem należy wykreślić jedynkę, bo ma ona tylko jeden dzielnik.
- Teraz pora na liczby podzielne przez 2 (z wyjątkiem 2). W ten sposób wykreśla się (odsiewa) prawie połowę liczb, którymi już nie trzeba się zajmować.
- Dalej należy kolejno wykreślić liczby podzielne przez 3 (z wyjątkiem 3).
- Liczba 4 została już odsiana, więc następna jest piątka.
- Zostało jeszcze odsianie liczb podzielnych przez 7 (z wyjątkiem 7), czyli 49, 77 i 91 – i zostaną wyłącznie liczby pierwsze.
LISTA KROKÓW I JEJ REALIZACJA W SCRATCHU
Utwórz w Scratchu projekt realizujący sito Eratostenesa dla liczb z zakresu od 1 do 100. Kieruj się opisanymi niżej krokami, które trzeba wykonać.
- Weź liczby naturalne od 1 do 100.
W Scratchu: utwórz listę Liczby i wypełnij ją liczbami od 1 do 100, utwórz pomocniczą zmienną liczba.
- Wykreśl 1.
W Scratchu: zamień 1 na liście na X. - Powtarzaj od 2 do liczby, której kwadrat jest większy od wybranego zakresu: weź kolejną niewykreśloną liczbę i wykreśl jej wielokrotności.
W Scratchu: utwórz zmienną dzielnik i ustaw ją na 2; powtarzaj, aż dzielnik do kwadratu będzie większy niż zakres: jeżeli element listy równy dzielnikowi nie jest równy X, to usuń jego wielokrotności i zmień dzielnik o 1.
Wykreślanie wielokrotności. Powtarzaj do końca zakresu liczb: jeżeli liczba nie jest wykreślona oraz liczba jest podzielna przez dzielnik, ale nie równa dzielnikowi, to wykreśl liczbę.
W Scratchu: zdefiniuj nowy blok Usuń wielokrotności wywoływany z parametrem dzielnik.
