{"id":"informatyka-2006-maj-matura-rozszerzona/zad/2","paper_id":"informatyka-2006-maj-matura-rozszerzona","number":"2","points":null,"ptype":"open","subject":"informatyka","category":"matura","year":2006,"month":"maj","level":"rozszerzona","text":"Zadanie 2. Liczby pierwsze (13 pkt)\nPoniżej przedstawiono algorytm wyznaczający wszystkie liczby pierwsze z przedziału [2, N],\nwykorzystujący metodę Sita Eratostenesa. Po zakończeniu wykonywania tego algorytmu, dla\nkażdego i = 2, 3, , N, zachodzi T[i]=0, jeśli i jest liczbą pierwszą, natomiast T[i]=1,\ngdy i jest liczbą złożoną.\nDane: Liczba naturalna\n2\nN ≥\nWynik: Tablica T[2 N], w której T[i] = 0, jeśli i jest liczbą pierwszą, natomiast T[i]=1,\ngdy i jest liczbą złożoną.\nKrok 1.\nDla i = 2, 3, , N wykonuj T[i] := 0\nKrok 2.\ni := 2\nKrok 3.\nJeżeli T[i] = 0 to przejdź do kroku 4, w przeciwnym razie przejdź do kroku 6\nKrok 4.\nj := 2 * i\nKrok 5.\nDopóki j ≤ N wykonuj\nT[j] := 1\nj := j + i\nKrok 6.\ni := i + 1\nKrok 7.\nJeżeli i < N, to przejdź do kroku 3, w przeciwnym razie zakończ wykonywanie\nalgorytmu\nUwaga: „:=” oznacza instrukcję przypisania.\na) Dane są: liczba naturalna\n1\n≥\nM\ni tablica A[1 M] zawierająca M liczb naturalnych\nz przedziału [2, N]. Korzystając z powyższego algorytmu, zaprojektuj algorytm,\nwyznaczający te liczby z przedziału [2, N], które nie są podzielne przez żadną z liczb\nA[1], , A[M]. Zapisz go w wybranej przez siebie notacji (lista kroków, schemat blokowy\nlub język programowania) wraz ze specyfikacją.\nArkusz I\n5\n6\nArkusz I\nb) Do algorytmu opisanego na początku zadania wprowadzamy modyfikacje, po których ma\non następującą postać:\nKrok 1.\nDla i = 2, 3, , N wykonuj T[i] := 0\nKrok 2.\ni := 2\nKrok 3.\nJeżeli T[i] = 0 to przejdź do kroku 4, w przeciwnym razie przejdź do kroku 6\nKrok 4.\nj := 2 * i\nKrok 5.\nDopóki j ≤ N wykonuj\nT[j] := T[j] + 1\nj := j + i\nKrok 6.\ni := i + 1\nKrok 7.\nJeżeli i < N, to przejdź do kroku 3, w przeciwnym razie zakończ wykonywanie\nalgorytmu\nPodaj, jakie będą wartości T[13], T[24], T[33] po uruchomieniu tak zmodyfikowanego\nalgorytmu dla N=100.\nPodaj, dla jakiej wartości T[i], dla i z przedziału [2, N], i jest liczbą pierwszą.\nNapisz, jaką własność liczb i = 2, ,N określają wartości T[i] po wykonaniu tak\nzmodyfikowanego algorytmu.\nArkusz I\n7\nc) Sito Eratostenesa służy do wyznaczania wszystkich liczb pierwszych z zadanego\nprzedziału [2, N]. Podaj w wybranej przez siebie notacji (lista kroków, schemat blokowy\nlub język programowania) inny algorytm, który sprawdza, czy podana liczba naturalna\nL>1 jest liczbą pierwszą. Zauważ, że chcemy sprawdzać pierwszość tylko liczby L,\nnatomiast nie jest konieczne sprawdzanie pierwszości liczb mniejszych od L. Przy ocenie\nTwojego algorytmu będzie brana pod uwagę jego złożoność czasowa.\nSpecyfikacja:\nDane: Liczba naturalna\n1\nL > .\nWynik: Komunikat „Tak”, jeśli L jest liczbą pierwszą, komunikat „Nie” w przeciwnym razie.\n8\nArkusz I\nPunktacja:\nCzęści zadania\nMaks.\na\n4\nb\n3\nc\n6\nRazem\n13\nArkusz I\n9","answer":null,"answer_text":"2. Rozwiązania\ni\nodpowiedzi\nzamieść\nw\nmiejscu\nna to przeznaczonym.","solution":null,"image":"img/informatyka-2006-maj-matura-rozszerzona/zad-2.webp","solution_image":null,"topics":null,"page_from":4,"source":"ocr","answer_source":null,"answer_text_source":"ocr","solution_source":null,"text_source":"ocr","source_label":"Informatyka · Matura · maj 2006 (rozszerzona)","subject_label":"Informatyka","category_label":"Matura","text_html":"

Zadanie 2. Liczby pierwsze (13 pkt)
Poniżej przedstawiono algorytm wyznaczający wszystkie liczby pierwsze z przedziału [2, N],
wykorzystujący metodę Sita Eratostenesa. Po zakończeniu wykonywania tego algorytmu, dla
każdego i = 2, 3, , N, zachodzi T[i]=0, jeśli i jest liczbą pierwszą, natomiast T[i]=1,
gdy i jest liczbą złożoną.
Dane: Liczba naturalna
2
N ≥
Wynik: Tablica T[2 N], w której T[i] = 0, jeśli i jest liczbą pierwszą, natomiast T[i]=1,
gdy i jest liczbą złożoną.
Krok 1.
Dla i = 2, 3, , N wykonuj T[i] := 0
Krok 2.
i := 2
Krok 3.
Jeżeli T[i] = 0 to przejdź do kroku 4, w przeciwnym razie przejdź do kroku 6
Krok 4.
j := 2 * i
Krok 5.
Dopóki j ≤ N wykonuj
T[j] := 1
j := j + i
Krok 6.
i := i + 1
Krok 7.
Jeżeli i < N, to przejdź do kroku 3, w przeciwnym razie zakończ wykonywanie
algorytmu
Uwaga: „:=” oznacza instrukcję przypisania.
a) Dane są: liczba naturalna
1
≥
M
i tablica A[1 M] zawierająca M liczb naturalnych
z przedziału [2, N]. Korzystając z powyższego algorytmu, zaprojektuj algorytm,
wyznaczający te liczby z przedziału [2, N], które nie są podzielne przez żadną z liczb
A[1], , A[M]. Zapisz go w wybranej przez siebie notacji (lista kroków, schemat blokowy
lub język programowania) wraz ze specyfikacją.
Arkusz I
5
6
Arkusz I
b) Do algorytmu opisanego na początku zadania wprowadzamy modyfikacje, po których ma
on następującą postać:
Krok 1.
Dla i = 2, 3, , N wykonuj T[i] := 0
Krok 2.
i := 2
Krok 3.
Jeżeli T[i] = 0 to przejdź do kroku 4, w przeciwnym razie przejdź do kroku 6
Krok 4.
j := 2 * i
Krok 5.
Dopóki j ≤ N wykonuj
T[j] := T[j] + 1
j := j + i
Krok 6.
i := i + 1
Krok 7.
Jeżeli i < N, to przejdź do kroku 3, w przeciwnym razie zakończ wykonywanie
algorytmu
Podaj, jakie będą wartości T[13], T[24], T[33] po uruchomieniu tak zmodyfikowanego
algorytmu dla N=100.
Podaj, dla jakiej wartości T[i], dla i z przedziału [2, N], i jest liczbą pierwszą.
Napisz, jaką własność liczb i = 2, ,N określają wartości T[i] po wykonaniu tak
zmodyfikowanego algorytmu.
Arkusz I
7
c) Sito Eratostenesa służy do wyznaczania wszystkich liczb pierwszych z zadanego
przedziału [2, N]. Podaj w wybranej przez siebie notacji (lista kroków, schemat blokowy
lub język programowania) inny algorytm, który sprawdza, czy podana liczba naturalna
L>1 jest liczbą pierwszą. Zauważ, że chcemy sprawdzać pierwszość tylko liczby L,
natomiast nie jest konieczne sprawdzanie pierwszości liczb mniejszych od L. Przy ocenie
Twojego algorytmu będzie brana pod uwagę jego złożoność czasowa.
Specyfikacja:
Dane: Liczba naturalna
1
L > .
Wynik: Komunikat „Tak”, jeśli L jest liczbą pierwszą, komunikat „Nie” w przeciwnym razie.
8
Arkusz I
Punktacja:
Części zadania
Maks.
a
4
b
3
c
6
Razem
13
Arkusz I
9

","answer_text_html":"
  1. Rozwiązania
\n

i
odpowiedzi
zamieść
w
miejscu
na to przeznaczonym.

","solutions":[]}