dlamaturzysty.info

zadania z informatyki - Praktyka w teorii

przedmiot: informatyka

Przykłady zadań rozwiązywanych na maturze bez użycia komputera.
Liczba zadań: 10. Liczba pytań: 34.

Zadania dostępne także w aplikacji Matura - testy i zadania, gdzie mogliśmy wprowadzić dodatkowe funkcje, np: dodawanie do powtórek, zapamiętywanie postępu nauki czy notatnik.
google_play_h56.png app_store_h56.png
Dziękujemy także developerom z firmy Geeknauts, którzy stworzyli tę aplikację

Zadanie: 1 2 3 4 5 6 7 8 9 10
Zadanie 1.
Bajtek i Bituś poznali starożytny chiński sposób testowania pierwszości liczby naturalnej n:

liczba n musi spełniać równanie
2n mod n = 2,
gdzie mod oznacza operator dzielenia modulo, czyli resztę z dzielenia całkowitego.

Uwaga: Starożytny chiński sposób bywa zawodny, istnieją liczby, które spełniają to równanie, a nie są pierwsze; natomiast jeśli równanie nie zachodzi, to n jest na pewno złożona. 

Chłopcy postanowili przetestować chińską metodą kolejne liczby n>=2, przeprowadzając obliczenia tylko na takich liczbach, które można reprezentować bez znaku na 8 bitach. co znaczy, że na każdym etapie obliczeń stosowali tylko liczby całkowite z zakresu od 0 do 255. 

Bajtek obliczał potęgi 2n dla kolejnych wartości n i dla obliczonej wartości wyznaczał resztę z dzielenia przez n.

Bituś skorzystał z praw arytmetyki modularnej. W każdym z kolejnych kroków obliczania potęgi, wynik iloczynu brał modulo n. Na przykład dla n=3 obliczenia wykonywał następująco:


Który z nich mógł przetestować pierwszość liczb w większym zakresie?
Podaj możliwie największą wartość n, dla której możliwe było przeprowadzenie testu pierwszości metodą każdego z chłopców.

W obliczeniach Bajtka nmax = ................
W obliczeniach Bitusia nmax = ...............
Następna strona

źródło: CKE
Polityka Prywatności