Zadanie 1. Liczby pierwsze w Bajtolandii

Na pewnej planecie zwanej Bajtolandią szczególne znaczenie mają liczby pierwszeliczba pierwszaliczby pierwsze. W pewnych specyficznych sytuacjach mieszkańcy tej planety potrzebują nie tyle informacji, czy podana liczba jest pierwsza, lecz jakie są liczby pierwsze mniejsze od podanej. Podawana liczba niekoniecznie musi być liczbą pierwszą.

Zapisz algorytm (w postaci listy kroków, za pomocą pseudokodu lub w wybranym języku programowania), który wyświetli wszystkie liczby pierwsze mniejsze od danej liczby limit.

Specyfikacja problemu:

Dane:

  • limit – liczba całkowita większa od 0

Wynik:

  • lista wszystkich liczb pierwszych mniejszych od limit

Uwaga: W zapisie algorytmu możesz wykorzystać tylko operacje arytmetyczne (dodawanie, odejmowanie, mnożenie, dzielenie, dzielenie całkowite, reszta z dzielenia), instrukcje porównania, instrukcje sterujące i przypisania do zmiennych lub samodzielnie napisane funkcje, wykorzystujące wyżej wymienione operacje.

Rozwiązanie iteracyjne:

Przedstawione zadanie rozwiążemy, stosując mechanizm iteracjiiteracjaiteracji. Wykorzystamy przy tym dwie pętle. Pierwsza z nich posłuży do wybierania kolejnych liczb naturalnych mniejszych od liczby przechowywanej w zmiennej limit. Sprawdzimy, które z nich są liczbami pierwszymi.

Aby ustalić, czy mamy do czynienia z liczbą pierwszą, wykorzystamy drugą zagnieżdżoną pętlę i instrukcję break. W pętli będziemy sprawdzać podzielność liczby przez kolejne liczby naturalne, zaczynając od liczby 2, a kończąc na liczbie, której kwadrat byłby większy od wartości przechowywanej w zmiennej liczba.

W przypadku, gdy badana liczba byłaby dzielnikiem, przerwiemy działanie wewnętrznej pętli za pomocą instrukcji break.

Oto zapis algorytmu w postaci pseudokodu:

Linia 1. liczba znak równości 2. Linia 2. dopóki liczba otwórz nawias ostrokątny limit wykonuj dwukropek. Linia 3. dzielnik znak równości 2. Linia 4. wypisac znak równości true. Linia 6. dopóki dzielnik asterysk dzielnik otwórz nawias ostrokątny znak równości liczba wykonuj dwukropek. Linia 7. jeżeli liczba mod dzielnik znak równości znak równości 0 wykonaj dwukropek. Linia 8. wypisac znak równości false. Linia 9. przerwij pętlę. Linia 10. dzielnik znak równości dzielnik plus 1. Linia 12. jeżeli wypisac znak równości znak równości true wykonaj dwukropek. Linia 13. wypisz liczba. Linia 15. liczba znak równości liczba plus 1.

Opis pseudokodu:

W linii numer 1 przypisujemy zmiennej liczba wartość początkową. Wynosi ona 2 i właśnie od niej zaczniemy sprawdzanie, czy mamy do czynienia z liczbą pierwszą. Zmiennej przypisujemy taką wartość, ponieważ liczba 2 jest najmniejszą liczbą pierwszą.

Następnie otwieramy zewnętrzną pętlę działającą do momentu, w którym zmienna liczba przyjmie wartość równą zmiennej limit (polecenie zwiększenia zmiennej liczba znalazło się w linii numer 15).

W linii 3. podajemy najmniejszy dzielnik, od którego zaczniemy sprawdzanie, czy badana liczba jest liczbą pierwszą. Ponieważ każda liczba naturalna dzieli się przez 1, wartość zmiennej dzielnik ustawiamy na 2.

W linii 4. zakładamy, że obecnie sprawdzana liczba jest liczbą pierwszą; wypiszemy ją na ekranie, jeśli nie znajdziemy jej dzielnika. Zmienna wypisac służy do przechowania informacji o tym, czy powinniśmy wyświetlić badaną liczbę. Inicjujemy ją wartością true.

Kolejna instrukcja (w linii numer 6) jest początkiem zagnieżdżonej pętli while. Pętla służy do iteracyjnego sprawdzania, czy wartość przechowywana w zmiennej dzielnik jest mniejsza lub równa pierwiastkowi kwadratowemu liczby przechowywanej w zmiennej liczba. Będziemy zwiększać wartość zmiennej dzielnik (polecenie w linii numer 11) do momentu, gdy stanie się ona większa od wartości pierwiastka liczby przechowywanej w zmiennej liczba. Kolejnych dzielników nie ma potrzeby sprawdzać.

Jeśli jednak spełniony zostanie warunek podzielności zmiennej liczba przez dzielnik (linia numer 7), ustawiamy wartość zmiennej wypisac na false. Oznacza to, że sprawdzanej liczby nie należy wyświetlać, ponieważ nie jest ona liczbą pierwszą. W takim właśnie przypadku używamy instrukcji przerwij (break), aby opuścić zagnieżdżoną pętlę.

Pozostaje sprawdzić (linia 12.), czy należy wyświetlić zmienną liczba. Jeżeli okaże się, że tak, wykonujemy instrukcję z linii numer 13.

Rozwiązanie wykorzystujące sito Eratostenesa:

Zadanie możemy rozwiązać, wykorzystując sito Eratostenesa. Algorytm omówiono w materiale Sito EratostenesaP7MwVxKT0Sito Eratostenesa.

Na potrzeby niniejszego rozwiązania przypomnijmy, że algorytm swoje działanie opiera na tablicy wartości logicznych o długości badanego przedziału. Początkowo każda komórka tablicy przechowuje wartość prawda.

Zaczynając od liczby 2, ustawiamy komórkom, których indeksy są jej wielokrotnościami, wartość fałsz – jest to operacja „wykreślenia” liczby. Proces powtarzamy dla kolejnych niewykreślonych liczb. Jeżeli liczba została wykreślona wcześniej (na przykład 4), oznacza to, że jej wielokrotności również zostały wykreślone – nie ma potrzeby powtarzania operacji. Algorytm kończy działanie, gdy liczba i, której wielokrotność wykreślamy, będzie większa od pierwiastka z rozmiaru sita.

Algorytm możemy przedstawić za pomocą następującego pseudokodu:

Linia 1. stwórz tablicę wartości logicznych sito otwórz nawias kwadratowy limit zamknij nawias kwadratowy. Linia 3. dla i znak równości 0 przecinek 1 przecinek 2 przecinek 3 kropka kropka kropka limit minus 1 wykonuj dwukropek. Linia 4. sito otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości prawda. Linia 6. i znak równości 2. Linia 7. dopóki i asterysk i otwórz nawias ostrokątny znak równości limit wykonuj dwukropek. Linia 8. jeżeli sito otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości znak równości prawda wykonaj dwukropek. Linia 9. j znak równości i asterysk i. Linia 10. dopóki j otwórz nawias ostrokątny limit wykonuj dwukropek. Linia 11. sito otwórz nawias kwadratowy j zamknij nawias kwadratowy znak równości fałsz. Linia 12. j znak równości j plus i. Linia 13. i znak równości i plus 1. Linia 15. dla a znak równości 2 przecinek 3 przecinek kropka kropka kropka limit minus 1 wykonuj dwukropek. Linia 16. jeżeli sito otwórz nawias kwadratowy a zamknij nawias kwadratowy znak równości znak równości prawda wykonaj dwukropek. Linia 17. wypisz a.

W 1. linii tworzymy tablice wartości logicznych o długości limit.

Kolejne linie: 3. i 4. służą do przygotowania tablicy do pełnienia funkcji sita. Następuje wypełnienie wszystkich komórek wartościami prawda. W tym momencie zakładamy, że każda liczba z zadanego przedziału jest pierwsza.

W linii 6. tworzymy zmienną i. Inicjalizujemy ją wartością 2. Zmienna i pełni funkcję iteratora – będzie wskazywać aktualnie przetwarzaną liczbę, której wielokrotności wykreślamy.

Wreszcie w 7. linii tworzymy pętlę dopóki. Będzie wykonywać się, do czasu aż i jest mniejsze od pierwiastka z długości tablicy lub równe temu pierwiastkowi. Autorzy zadania ściśle określają dozwolone operacje matematyczne – na tej liście nie ma pierwiastkowania. Zauważmy, że jeżeli obie strony nierówności podniesiemy do kwadratu, uzyskamy zaprezentowany warunek pętli: i * i <= limit.

Przedstawiona w linii 8. instrukcja warunkowa sprawdza, czy badana liczba jest pierwsza – jeżeli została wykreślona wcześniej (jest złożona) nie ma sensu ponownie wykreślać jej wielokrotności. Jeżeli nie została wykreślona, przechodzimy do instrukcji w linii 13.

Stworzona w linii 9. zmienna j przechowuje kwadrat liczby i – od tej wielokrotności rozpoczniemy wykreślanie.

W liniach: 10., 11. i 12. następuje proces wykreślenia wielokrotności. Dopóki zmienna j jest mniejsza od zmiennej limit, następuje zmiana wartości komórek tablicy sito[j] na fałsz. Liczby te na pewno nie są pierwsze. Po każdej operacji wykreślenia zwiększamy wartość zmiennej ji – przechodzimy do kolejnej wielokrotności.

Po wyjściu z wewnętrznej pętli zwiększamy w linii 13. wartość zmiennej i o 1.

Następnie wypisujemy liczby pierwsze mniejsze od limit. W tym celu deklarujemy w linii 15. pętlę dla, której iterator a będzie przyjmował kolejne liczby od 2 do limit - 1.

Stworzona w linii 16. instrukcja warunkowa sprawdza, czy pod wskazywanym przez iterator a indeksem kryje się wartość prawda (liczba nie została wykreślona, więc jest pierwsza). Jeżeli warunek jest prawdziwy, wówczas wypisujemy wartość a (linia 17.).

Słownik

iteracja
iteracja

słowo pochodzące od łacińskiego iteratio (powtarzanie); oznacza powtarzanie w pętli tych samych instrukcji, aż do spełnienia pewnego warunku

liczba pierwsza
liczba pierwsza

liczba naturalna większa od 1, która ma tylko dwa dzielniki naturalne: 1 oraz siebie samą