Temat: Przesiewanie liczb pierwszych

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

1. Najpierw należy wypisać wszystkie liczby w podanym zakresie, np. od 1 do 100.
2. Potem należy wykreślić jedynkę, bo ma ona tylko jeden dzielnik.
3. 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ć.
4. Dalej należy kolejno wykreślić liczby podzielne przez 3 (z wyjątkiem 3).
5. Liczba 4 została już odsiana, więc następna jest piątka.
6. 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.