Czego się nauczysz
Nauczysz się wyznaczać naraz wszystkie liczby pierwsze do n metodą sita Eratostenesa, przyspieszysz ją dwiema prostymi zmianami i wykorzystasz gotowe sito do odpowiadania na wiele pytań o pierwszość.
Po co ci to na maturze
Gdy w pliku jest tysiąc liczb do miliona i o każdą trzeba zapytać, czy jest pierwsza, sprawdzanie każdej osobno trwa długo. Sito przygotowuje odpowiedź dla wszystkich liczb naraz, a potem każde pytanie to jeden odczyt z listy.
Etapy lekcji
Spis lekcji
Teoria
5 rozdziałówNie zaczęte- 1.1Skreślanie wielokrotnościNa kartce z liczbami każda liczba pierwsza skreśla swoje wielokrotności, a bez kreski zostają same liczby pierwsze.
- 1.2Sito w PythonieKartkę zastępuje lista wartości True i False, a kreska przy liczbie k to wpisanie False pod indeksem k.
- 1.3Szybsze sito: od kwadratu do pierwiastkaSkreślanie wystarczy zacząć od kwadratu liczby, a pętlę zakończyć na pierwiastku z n, bo reszta ma już kreski.
- 1.4Sito jako tablica odpowiedziGotowe sito od razu mówi, czy liczba do n jest pierwsza, więc opłaca się, gdy pytań jest dużo.
- 1.5PodsumowanieNajważniejsze rzeczy z każdego rozdziału na jednej stronie, do szybkiej powtórki.