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:

liczba = 2
dopóki liczba < limit wykonuj:
	dzielnik = 2
	wypisac = true

	dopóki dzielnik * dzielnik <= liczba wykonuj:
		jeżeli liczba mod dzielnik == 0 wykonaj:
			wypisac = false
			przerwij pętlę
		dzielnik = dzielnik + 1

	jeżeli wypisac == true wykonaj:
		wypisz liczba

	liczba = liczba + 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:

stwórz tablicę wartości logicznych sito[limit]

dla i = 0, 1, 2, 3 ... limit - 1 wykonuj:
	sito[i] = prawda

i = 2
dopóki i * i <= limit wykonuj:
	jeżeli sito[i] == prawda wykonaj:
    	j = i * i
        dopóki j < limit wykonuj:
        	sito[j] = fałsz
            j = j + i
    i = i + 1

dla a = 2, 3, ... limit - 1 wykonuj:
	jeżeli sito[a] == prawda wykonaj:
    	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 j o i – 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