Liczby pierwsze: test pierwszości, sito Eratostenesa i rozkład na czynniki

Liczby pierwsze to stały element zadań programistycznych na maturze z informatyki: trzeba sprawdzić, które liczby z pliku są pierwsze, rozłożyć liczbę na czynniki albo policzyć liczby o określonej własności. Podstawa programowa wymienia badanie pierwszości liczby, generowanie liczb pierwszych metodą sita Eratostenesa i rozkładanie liczby na czynniki pierwsze — ten materiał łączy te trzy algorytmy.

Zaczynasz od definicji: liczba pierwsza jest większa od 1 i ma dokładnie dwa dzielniki, więc ani 0, ani 1 nie są pierwsze, a 2 jest najmniejszą liczbą pierwszą. Potem test pierwszości metodą prób: wystarczy sprawdzać dzielniki od 2 do $\sqrt{n}$, bo jeśli $n=a\cdot b$, to jeden z czynników nie przekracza pierwiastka. Stąd warunek pętli $d\cdot d\le n$ i złożoność $O(\sqrt{n})$. Analizujesz też krótką funkcję w C++ i szukasz argumentu, dla którego daje błędny wynik — to typowy sposób sprawdzania, czy rozumiesz przypadki brzegowe.

Druga część to sito Eratostenesa: dlaczego wykreślanie wielokrotności liczby $p$ zaczynamy od $p^2$, kiedy można przerwać pracę i ile pamięci zajmuje tablica sita. Sito jest opłacalne, gdy potrzebujesz wszystkich liczb pierwszych z zakresu — działa w czasie $O(n\log \log n)$, czyli znacznie szybciej niż osobne testowanie każdej liczby.

Trzecia część to rozkład na czynniki pierwsze. Śledzisz program w Pythonie, który dzieli liczbę przez kolejne dzielniki tak długo, jak się da, i wypisuje listę czynników. Z rozkładu wyznaczasz liczbę dzielników: dla $n=p_1^{a_1}\cdot p_2^{a_2}$ jest ich $(a_1+1)(a_2+1)$.

Materiał oferuje cztery formy pracy. Quiz zawiera pytania o własności algorytmów, rachunki i analizę kodu z wyjaśnieniem. Fiszki utrwalają definicje, warunki pętli i złożoności. Egzamin ustny w formie rozmowy z egzaminatorem sprawdza, czy umiesz objaśnić działanie algorytmu i uzasadnić jego poprawność. Praca pisemna do wydruku zawiera zadania otwarte: ręczne wykonanie sita, rozkład liczby, zapis algorytmu w pseudokodzie lub w wybranym języku programowania (C++, Python lub Java).

Każde zadanie jest oryginalnym ćwiczeniem do samodzielnej nauki i zawiera wszystkie potrzebne dane; wyniki programów zostały sprawdzone przez ich uruchomienie.

• Uzasadniasz, dlaczego w teście pierwszości wystarczy sprawdzać dzielniki do pierwiastka z n.
• Wykonujesz sito Eratostenesa i wyjaśniasz, od której liczby i do kiedy wykreślać wielokrotności.
• Rozkładasz liczbę na czynniki pierwsze i wyznaczasz z rozkładu liczbę jej dzielników.
• Znajdujesz błędy w przypadkach brzegowych gotowych implementacji.
• Porównujesz złożoność testu pierwszości i sita Eratostenesa.

Materiał ćwiczeniowy przygotowany przez Zestly.