Przesiewanie liczb pierwszych

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.

Skip to content