Do generacji liczb pierwszych wykorzystamy podaną w poprzednim rozdziale definicję liczby pierwszej. Algorytm będzie składał się z dwóch oddzielnych części. Pierwsza część bada, czy przekazana jej liczba jest liczbą pierwszą. Druga typuje liczby pierwsze, przekazuje je do zbadania pierwszej części i jeśli otrzyma pozytywną odpowiedź, wyprowadza je jako wynik. Takie podejście do rozwiązania problemu ułatwi nam wprowadzanie optymalizacji w następnych wersjach algorytmu.
Funkcja Testuj ma za zadanie stwierdzenie, czy przekazana jej jako parametr liczba naturalna p jest liczbą pierwszą. Tego typu zadanie nazywa się badaniem pierwszości liczby (ang. primality testing).
Dane wejściowe
p - badana liczba przekazana do funkcji Testuj jako parametr, p N Dane wyjściowe
Wynik logiczny true, jeśli liczba p jest liczbą pierwszą lub wynik false w przypadku przeciwnym. Wynik stanowi wartość funkcji Testuj.
Zmienne pomocnicze
i - pełni rolę licznika pętli oraz kolejnych dzielników liczby p, i N
krok 1: Dla i = 2,3,...,p - 1 jeśli (p mod i) = 0, to Testuj(p) false i zakończ algorytm krok 2: Testuj(p) true i zakończ algorytm
Na początku algorytmu inicjujemy pętlę kontrolowaną przez zmienną i, która początkowo przyjmuje wartość 2. Zmienna ta pełni również rolę kolejnych dzielników liczby p.
Pętla wykonuje się przy i mniejszym od p. W przeciwnym razie zostaje przerwana i algorytm kończy się zwrotem wartości logicznej true (prawda), co oznacza, iż żadna liczba z przedziału od 2 do p - 1 nie dzieli p. Zatem p jest liczbą pierwszą.
Wewnątrz pętli sprawdzamy, czy dzielnik i dzieli bez reszty liczbę p. Jeśli tak, to pętla również ulega przerwaniu i algorytm zwraca wartość logiczną false (fałsz) - liczba p nie jest pierwsza.
Jeśli reszta z dzielenia p przez i jest różna od 0, to zwiększamy i o 1 (bierzemy następny dzielnik) i wracamy na początek pętli.
Posiadając funkcję testującą pierwszość możemy utworzyć główny algorytm generacji liczb pierwszych. Algorytm ten będzie generował zadaną ilość początkowych liczb pierwszych.
Algorytm wykorzystuje poprzednio zdefiniowaną funkcję badania pierwszości liczby do generacji kolejnych liczb pierwszych.
Dane wejściowe
ile - określa ilość początkowych liczb pierwszych, które należy wygenerować, ile N Dane wyjściowe
Kolejno znalezione liczby pierwsze pi , i = 1,2,3,...,ile.
Zmienne pomocnicze
lp - zlicza znalezione liczby pierwsze, lp N p - zawiera kolejno testowane liczby, p N, p = 2,3,...
krok 1: Czytaj ile krok 2: lp 0; p 2 krok 3: Dopóki lp < ile wykonuj kroki 4...5. Inaczej zakończ algorytm. krok 4: Jeśli Testuj(p) = true, to wypisz p i zwiększ lp lp + 1 krok 5: Zwiększ p p + 1 i kontynuuj pętlę od kroku 3
Najpierw odczytujemy ile liczb pierwszych ma znaleźć nasz algorytm. Informacja ta zostanie umieszczona w zmiennej ile. Następnie inicjujemy licznik liczb pierwszych lp na 0 (nie znaleziono jeszcze żadnej liczby pierwszej) oraz p na 2 (pierwsza możliwa liczba pierwsza).
Teraz rozpoczyna się pętla warunkowa, która jest kontynuowana przy warunku lp < ile. Warunek ten będzie spełniony do momentu znalezienia zadanej ilości liczb pierwszych. Wtedy pętla zostanie przerwana i algorytm zakończy swoje działanie.
Wewnątrz pętli wywołujemy funkcję Testuj z parametrem p. Funkcja ta zbada, czy przekazany jej parametr jest liczbą pierwszą. Jeśli tak, to zwróci wartość logiczną true. W takim przypadku wypiszemy p i zwiększymy o 1 licznik lp. Jeśli p nie jest liczbą pierwszą, to funkcja Testuj zwróci wartość logiczną false. Wtedy pominiemy wypisanie p i zwiększenie o 1 licznika lp.
Pętla zawsze kończy się zwiększeniem o 1 liczby p, czyli przejściem do kolejnej wartości, która potencjalnie może być liczbą pierwszą. Po tej operacji przechodzimy na początek pętli i cały opisany cykl rozpoczyna się od nowa.
Poniższe, przykładowe programy są praktyczną realizacją omawianego w tym rozdziale algorytmu. Zapewne można je napisać bardziej efektywnie. To już twoje zadanie. Dokładny opis stosowanych środowisk programowania znajdziesz we wstępie. Programy przed opublikowaniem w serwisie edukacyjnym zostały dokładnie przetestowane. Jeśli jednak znajdziesz jakąś usterkę (co zawsze może się zdarzyć), to prześlij o niej informację do autora. Pozwoli to ulepszyć nasze artykuły. Będziemy Ci za to wdzięczni.
Wydruk z uruchomionego programu |
---|
Generator zadanej ilości liczb pierwszych |
Microsoft Visual Basic 2005 Express Edition |
Dla celów badawczych zbierzemy dane o ilości wykonywanych operacji modulo. Wyposażymy program w odpowiedni licznik, którego stan będzie zwiększany każdorazowo przy wykonywaniu operacji modulo. Na końcu wyświetlimy stan licznika. Oto konieczne modyfikacje programu w Delphi:
Na początku programu dopisujemy deklarację zmiennej lom - licznika operacji modulo. Ponieważ liczba operacji modulo może przekraczać zakres typu cardinal (232 - 1), wybieramy rozszerzony typ zmiennoprzecinkowy extended, który daje dokładność około 19...20 cyfr znaczących.
// Program generacji liczb pierwszych
// (C)2004 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//-----------------------------------
program glp;
{$APPTYPE CONSOLE}
var
lom : extended; // licznik operacji moduloDruga zmiana polega na modyfikacji funkcji Testuj, aby w przy każdej operacji modulo następowało zwiększenie o 1 licznika lom.
// Funkcja sprawdza, czy przekazana jako parametr
// liczba p jest liczbą pierwszą. Jeśli tak, to
// zwraca w wyniku true, przeciwnie zwraca false
//-----------------------------------------------
function Testuj(p : cardinal) : boolean;
var
i : cardinal;
begin
Testuj := true;
i := 2;
while i < p do
begin
lom := lom + 1; // Tutaj jest zmiana
if p mod i = 0 then
begin
Testuj := false; break;
end
else
i := i + 1;
end;
end;Trzecią zmianę wprowadzamy do programu głównego. Ma ona na celu zainicjowanie licznika lom na 0 przed rozpoczęciem zliczania operacji modulo oraz wyświetlenie jego stanu po wykonaniu zadania przez program.
//----------------------------------
// Tutaj rozpoczynamy program główny
//----------------------------------
var
ile,lp,p : cardinal;
begin
writeln('Generator zadanej ilosci liczb pierwszych');
writeln('-----------------------------------------');
writeln('(C)2004 mgr Jerzy Walaszek I LO Tarnow');
writeln;
write('Ile liczb wygenerowac ? : '); readln(ile);
writeln;
lp := 0; p := 2;
lom := 0; // Tutaj jest zmiana
while lp < ile do
begin
if Testuj(p) then
begin
write(p : 8); lp := lp + 1;
end;
p := p + 1;
end;
writeln;
writeln('Liczba operacji modulo : ',lom:15:0); // Tutaj jest zmiana
writeln;
write('Klawisz Enter = KONIEC'); readln; writeln;
end.Wyniki uzyskane w tak zmodyfikowanym programie zebraliśmy w poniższej tabeli.
Wyniki badania ilości wykonanych operacji modulo Ilość
l. pierw.Ilość
op. moduloWzrost 10 134 - 100 24984 186,448 1000 3711627 148,560 10000 497007180 133,905 100000 62284747034 125,320 W pierwszej kolumnie znajduje się ilość generowanych przez program liczb pierwszych. Ilość ta w każdym wierszu tabeli wzrasta dziesięciokrotnie. Z uwagi na niską efektywność prezentowanego algorytmu zakończyliśmy na liczbie 100000. Wyznaczenie tej ilości liczb pierwszych zajęło naszemu komputerowi około 40 minut ciągłej pracy.
W drugiej kolumnie umieściliśmy ilość wykonanych przez program operacji modulo do wyznaczenia zadanej ilości liczb pierwszych.
W trzeciej kolumnie obliczyliśmy przyrost wykonanych operacji modulo w dwóch sąsiednich wierszach tabeli, np.:
24984 : 134 = 186,448
3711627 : 24984 = 148,560
497007180 : 3711627 = 133,905, itd.
Przeanalizuj dane zawarte w powyższej tabeli i wyciągnij wnioski na temat klasy złożoności obliczeniowej prezentowanego w tym rozdziale algorytmu.
GNU Free Documentation License.
Źródło: mgr Jerzy Wałaszek