W opracowaniu naszym zamieściliśmy podstawowe sposoby znajdowania liczb pierwszych przy pomocy komputerów oraz zwróciliśmy uwagę na kilka ich ważnych zastosowań - np. w kryptologii do szyfrowania informacji. Liczby pierwsze odgrywają ogromną rolę we współczesnej informatyce i znajomość algorytmów generacji liczb pierwszych należy do podstaw wiedzy informatycznej.
We wstępie podaliśmy podstawowe definicje liczb pierwszych, które mają istotne znaczenie przy ich znajdowaniu za pomocą komputera. Najpierw wyszliśmy z podstawowej definicji:
Liczba pierwsza jest liczbą naturalną, która posiada dokładnie dwa różne podzielniki - 1 oraz samą siebie.
Jednakże definicja ta nie jest odpowiednia do wykorzystania w programach poszukujących liczb pierwszych. Dlatego zmieniliśmy ją na definicję równoważną, lecz dla nas bardziej użyteczną:
Liczba pierwsza jest liczbą naturalną, dla której reszta z dzielenia jej przez każdą liczbę większą od jeden i mniejszą od badanej liczby jest większa od zera. Oznacza to, iż żadna z tych liczb nie dzieli całkowitą liczbę razy badanej liczby.
Taka definicja daje nam istotne wskazówki, jak poszukiwać liczb pierwszych. Jednakże algorytm oparty bezpośrednio na niej miałby złożoność obliczeniową O(n2). Dlatego rozważyliśmy w dalszym toku rozkład czynników pierwszych liczb naturalnych i doszliśmy do wniosku, iż wystarczy sprawdzać podzielność przez liczby z przedziału od 2 do pierwiastka z badanej liczby. Dzięki temu podejściu i kilku innych usprawnieniach znacznie zmniejsza się ilość niezbędnych obliczeń.
W dalszej kolejności zaprezentowaliśmy programy w różnych językach programowania, które na podstawie tej definicji wyznaczają zadaną ilość liczb pierwszych. Zwróćcie uwagę na istotną kolejność powstawania tych programów:
ANALIZA - ALGORYTM - PROGRAM
- Najpierw dokonaliśmy analizy problemu. Wyciągnęliśmy odpowiednie wnioski oraz sformułowaliśmy użyteczne definicje, które posłużyły za bazę konstrukcji algorytmu.
- Na podstawie analizy problemu ułożyliśmy algorytm. Na tym etapie nie jest jeszcze istotny język programowania. Algorytm określa jedynie postać danych oraz niezbędne operacje nad nimi, które należy wykonać, aby rozwiązać dany problem. Jest to najistotniejszy punkt całego procesu tworzenia oprogramowania. Zły, niedopracowany algorytm będzie powodował, iż program powstały na jego bazie nie spełni pokładanych w nim nadziei.
- Na podstawie ułożonego algorytmu utworzyliśmy odpowiednie programy.
Zwracam na to uwagę, ponieważ wieloletnie obserwacje poczynań uczniów prowadzą do wniosku, iż zapominacie o dwóch pierwszych punktach próbując od razu tworzyć program bez odpowiedniej analizy problemu i przygotowania algorytmu. Nie muszę chyba dodawać, iż takie postępowanie w większości przypadków prowadzi do porażki (jeśli przyjrzymy się różnym projektom "profesjonalnych" firm softwarowych, to u nich też prawdopodobnie programiści zapominają o analizie i algorytmie). Dlatego zawsze postępujcie wg schematu: ANALIZA-ALGORYTM-PROGRAM. Unikniecie wtedy wielu pułapek i niespodzianek, a utworzony program będzie naprawdę wysokiej jakości.
W następnym rozdziale opisaliśmy bardzo stary algorytm wyszukiwania liczb pierwszych polegający na eliminacji ze zbioru liczb naturalnych liczb złożonych. Algorytm ten nosi nazwę Sita Eratostenesa i ma ponad 2000 lat. Jest naprawdę szybki i efektywny, jeśli mamy wyszukać liczby w ograniczonym zbiorze. Co więcej algorytm ten nie wymaga w ogóle sprawdzania podzielności, zatem wykonuje się błyskawicznie.
Dalej omówiliśmy algorytm Euklidesa znajdowania Największego Wspólnego Podzielnika dwóch liczb. Algorytm ten posiada liczne zastosowania (np. przy szyfrowaniu informacji). My użyliśmy go do skracania ułamków oraz znajdowania NWD 3 liczb.
W wielu zastosowaniach występuje potrzeba rozbijania liczb naturalnych na iloczyn czynników pierwszych. Omówiliśmy dosyć ciekawy algorytm, który tego dokonuje poprzez sprawdzenie podzielności. Tutaj również przydała się analiza rozkładu czynników pierwszych, dzięki czemu algorytm uległ znacznemu uproszczeniu i działa szybko nawet dla dużych liczb.
Kolejnym zagadnieniem są liczby pseudolosowe oraz metody ich generacji. Ograniczyliśmy się jedynie do generatorów liniowych. Oczywiście sposobów generacji tych liczb jest obecnie bardzo dużo. Dociekliwy czytelnik sam może wyszukać je w sieci Internet. Liczby pseudolosowe zastosowaliśmy do szyfrowania informacji. Prezentowany system szyfrujący kluczem symetrycznym ma jedynie znaczenie dydaktyczne. W praktyce zostałby bardzo szybko złamany.
O wiele bardziej zaawansowanym systemem szyfrowania jest system RSA, który omówiliśmy bardzo szczegółowo w ostatnim rozdziale. Na podstawie tego systemu powstały obecnie używane systemy zabezpieczeń danych w sieci Internet. Dzięki nim mogą dochodzić do skutku różne transakcje poprzez sieć bez ryzyka ich ujawnienia osobom postronnym. W rozdziale tym umieściliśmy prostą aplikację, która pozwala generować klucze RSA oraz szyfrować i rozszyfrowywać informację.
Mamy nadzieję, iż nasz artykuł przyczynił się do lepszego zrozumienia liczb pierwszych oraz ich wpływu na współczesną informatykę.
4 stycznia, 2004
mgr J.Wałaszek
Zadanie nr 1
Zaprojektuj algorytm i napisz na jego podstawie program, który wylicza ilość liczb pierwszych pomiędzy dwoma wczytanymi liczbami naturalnymi. Np dla 6 i 25 wynik powinien być równy:
6 7 11 13 17 19 23 25 - wynik 6.
Zadanie nr 2
Zaprojektuj algorytm i napisz na jego podstawie program, który oblicza sumę n kolejnych liczb pierwszych.
Np. dla n = 5 wynik powinien być równy:
2 + 3 + 5 + 7 + 11 = 28
Zadanie nr 3
Zaprojektuj algorytm i napisz na jego podstawie program, który dokonuje rozbioru podanej liczby naturalnej na jej czynniki pierwsze i wyszukuje wśród nich czynnik, który powtarza się największą ilość razy. Jeśli takich czynników będzie kilka, to powinien zostać wybrany największy z nich. Np.:
24 = 2 x 2 x 2 x 3 - wynik 2.
90 = 2 x 3 x 3 x 5 - wynik 3
Zadanie nr 1
Udowodniono, iż liczby parzyste od 4 do 100 000 000 można przedstawić w postaci sumy dwóch liczb pierwszych. Na przykład:
4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5, 12 = 5 + 7, 14 = 3 + 11, itd.
Zaprojektuj algorytm, a następnie utwórz na jego podstawie program w dowolnie wybranym języku programowania, który odczyta z klawiatury liczbę, sprawdzi czy jest ona parzysta i należy do przedziału od 4 do 100 000 000, a następnie przedstawi ją w postaci sumy dwóch liczb pierwszych.
Zadanie nr 2
Mamy daną liczbę zbudowaną z dziewięciu cyfr o następującej wartości 123456789. Zmieniając położenie tych cyfr możemy otrzymywać inne 9 cyfrowe liczby, np: 987654321, 593761482, 384675291 itd. Ułóż algorytm oraz napisz na jego podstawie program w dowolnie wybranym języku programowania, który obliczy, ile z tych liczb jest liczbami pierwszymi.
Zadanie nr 3
Pole pewnego prostokąta wyraża się liczbą naturalną. Zaprojektuj algorytm, a następnie napisz na jego podstawie program w dowolnym języku programowania, który odczyta to pole, a następnie wyświetli na ekranie wszystkie kombinację wymiarów prostokąta, które są liczbami naturalnymi (wymiary powtarzające się należy eliminować). Na przykład:
Pole wynosi 12:
12 = 1 x 12
12 = 2 x 6
12 = 3 x 4
- D. Knuth: The Art of Computer Programming - Volume 1 - Fundamental Algorithms, Addison-Wesley, 1969.
- Praca zbiorowa: Encyklopedia szkolna - Matematyka, Wydawnictwa Szkolne i Pedagogiczne, Warszawa 1989.
- M. Dryja, J. Jankowska: Przegląd metod i algorytmów numerycznych. WT, Warszawa 1988
- N. Writh: Algorytmy+struktury danych=program. WNT 1998.
- J. Grębosz (absolwent I LO z 1974): Symfonia C++, Tom I, II i III, Oficyna Kalimach, Kraków 1999.
- B. Stroustrup: Język C++.WNT, Warszawa 1995.
- A. Marciniak: Object Pascal w pakiecie Borland Delphi 3 i 4, NAKOM 1999
- A. Marciniak: Turbo Pascal 5.5, NAKOM 1991.
- A. Marciniak: Turbo Pascal 7, NAKOM 1994.
- T. M. Sadowski: Praktyczny kurs Turbo Pascala. Helion 1996.
- J. Zahorski: Turbo Pascal 7.0,Helion 1997.
Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.
Źródło: mgr Jerzy Wałaszek