obrazek

Prezentowane materiały są przeznaczone dla uczniów szkół ponadgimnazjalnych.
Autor artykułu: mgr Jerzy Wałaszek, wersja 1.0

obrazek

Generacja liczb pierwszych przez sprawdzanie podzielności

Definicja liczby pierwszej

Liczba pierwsza (ang. prime number) jest liczbą naturalną, która posiada dokładnie dwa różne podzielniki - liczbę 1 oraz samą siebie.

Przykłady liczb pierwszych:

2, 3, 5, 7, 11, 13, 17, 19, ...

Liczba 1 nie jest liczbą pierwszą. Co prawda dzieli się przez 1 i przez samą siebie, lecz jest to ten sam podzielnik a nie dwa różne, jak wymaga definicja.

Liczba zero również nie jest liczbą pierwszą, ponieważ nie dzieli się przez siebie samą.

Wynika z tego iż liczby pierwsze zawierają się w przedziale liczb naturalnych <2, ∞).

Dowód Euklidesa na nieskończoność zbioru liczb pierwszych

Zbiór liczb naturalnych N można podzielić na zbiór liczb pierwszych oraz zbiór liczb złożonych, czyli takich, które są podzielne przez inne liczby niż 1 i same siebie. Powstaje pytanie, czy zbiór liczb pierwszych jest skończony albo nieskończony. Odpowiedź dał słynny matematyk starożytnej Grecji, Euklides. Problem ten rozwiązał w sposób następujący:

Euklides założył, iż wszystkich liczb pierwszych jest skończona ilość n. Tworzą one zatem zbiór skończony:

P = {p₁, p₂, p₃, ..., p_n-1, p_n}, gdzie p_i, dla i = 1,2,...,n oznacza kolejne liczby pierwsze.

Założenie to oznacza, iż nie istnieją żadne inne liczby pierwsze poza liczbami ze zbioru P.

Teraz Euklides utworzył liczbę E, zwaną liczbą Euklidesa:

E = p₁ × p₂ × p₃ × ... × p_n-1 × p_n + 1

Liczba Euklidesa jest równa iloczynowi wszystkich liczb pierwszych ze zbioru P powiększonemu o 1. Posiada ona bardzo istotną własność: żadna liczba pierwsza ze zbioru P nie dzieli liczby E bez reszty. Wynika to bezpośrednio z definicji liczby E: dla dowolnej liczby p_k, 1 ≤ k ≤ n, należącej do zbioru P mamy:

obrazek

Ułamek 1 / p_k jest zawsze mniejszy od 1. Zatem wynik dzielenia nie jest liczbą całkowitą. Wynika z tego, iż żadna liczba pierwsza ze zbioru P nie dzieli bez reszty liczby E. Zatem:

Liczba E jest sama liczbą pierwszą lub
Liczbę E dzieli liczba pierwsza nie zawarta w zbiorze P.
Trzeciej możliwości nie ma.

W obu możliwych przypadkach dostajemy nową liczbę pierwszą, której nie ma w zbiorze P. Przeczy to założeniu, iż zbiór P zawierał wszystkie liczby pierwsze. W ten sposób Euklides udowodnił, iż zbiór liczb pierwszych jest nieskończony.

Sprawdzanie pierwszości

Pierwszość (ang. primality) jest własnością liczby naturalnej, która mówi, iż dana liczba jest liczbą pierwszą. Sprawdzenie pierwszości polega na zbadaniu, czy dana liczba naturalna jest liczbą pierwszą. Podana na początku rozdziału definicja liczby pierwszej nie jest tutaj specjalnie przydatna - każda liczba naturalna dzieli się przez 1 i przez siebie samą. Zatem musimy oprzeć algorytm na eliminacji liczb złożonych.

Liczba naturalna n jest liczbą złożoną, jeśli dzieli się bez reszty przez liczbę różną od 1 i różną od n.

Pierwszy algorytm będzie działał wg następującej idei:

Liczbę n będziemy próbowali dzielić przez kolejne liczby naturalne z przedziału od 2 do n-1. Jeśli któraś z tych liczb będzie dzieliła n bez reszty, to liczba n jest liczbą złożoną (zatem nie pierwszą) i algorytm możemy zakończyć z wynikiem negatywnym. Jeśli żadna z liczb od 2 do n-1 nie dzieli liczby n, to n jest liczbą pierwszą. Algorytm kończymy z wynikiem pozytywnym.

Algorytm sprawdzania pierwszości

Dane wejściowe:

n - liczby naturalna, której pierwszość badamy

Dane wyjściowe:

true - liczba n jest pierwsza
false - liczba n jest złożona

Dane pomocnicze:

i - kolejne podzielniki liczby n, i = 2, 3, ..., n-1

Lista kroków:

K01: Czytaj n
K01: Dla i = 2,3,...,n - 1 jeśli n mod i = 0, to zakończ zwracając false
K02: Zakończ zwracając true

Schemat blokowy:

obrazek

Program w języku C++:

Ćwiczenie na lekcji

Generowanie liczb pierwszych

Gdy wiemy już jak sprawdzić pierwszość liczby naturalnej, możemy wykorzystać tę wiedzę do wygenerowania zadanej ilości liczb pierwszych lub liczb pierwszych z zadanego zakresu:

Generujemy odpowiednią ilość kolejnych liczb naturalnych. Każdą wygenerowaną liczbę naturalną testujemy na pierwszość. Jeśli test da wynik pozytywny, liczbę wypisujemy.

Algorytm generacji wszystkich liczb pierwszych z zakresu od 2 do n

Dane wejściowe:

n - liczba naturalna określająca górny kraniec przedziału generacji liczb pierwszych

Dane wyjściowe:

Kolejne liczby pierwsze leżące w przedziale od 2 do n.

Dane pomocnicze:

i - kolejne liczby naturalne z przedziału od 2 do n
isPrime(x) - funkcja zwracająca true, gdy x jest pierwsze, lub false, gdy x jest złożone

Lista kroków:

K01: Czytaj n
K01: Dla i = 2,3,...,n jeśli isPrime(i), to Pisz i
K02: Zakończ

Schemat blokowy:

obrazek

Program w języku C++:

Ćwiczenie na lekcji

Algorytm generacji kolejnych n liczb pierwszych

Dane wejściowe:

n - liczba naturalna określająca górny kraniec przedziału generacji liczb pierwszych

Dane wyjściowe:

n kolejnych liczb pierwszych

Dane pomocnicze:

i - kolejne liczby naturalne
isPrime(x) - funkcja zwracająca true, gdy x jest pierwsze, lub false, gdy x jest złożone

Lista kroków:

K01: Czytaj n
K02: i ← 2
K03: Dopóki n > 0 wykonuj K04...K07
K04:     Jeśli isPrime(i) = false, to idź do K07
K05:     Pisz i
K06:     n ← n - 1
K07:     i ← i + 1
K08: Zakończ

Schemat blokowy:

obrazek

Program w języku C++:

Ćwiczenie na lekcji

Ulepszenie algorytmu testowania pierwszości

Podany na początku rozdziału algorytm sprawdzania pierwszości nie jest specjalnie efektywny.

Uruchom program generacji liczb pierwszych i każ wygenerować je w przedziale od 2 do 1000000. Zanotuj sobie czas pracy programu.

Dla każdej testowanej liczby n funkcja isPrime() musi wykonać około n dzieleń, aby stwierdzić, że n jest liczbą pierwszą. Czy można to usprawnić? Można:

Jeśli n jest liczbą pierwszą, to oczywiście n nie jest podzielne przez żadną z liczb z przedziału od 2 do n - 1 (dla n = 2 pętla testująca nie wykonuje ani jednego obiegu, ponieważ nie jest spełniony warunek jej kontynuacji).

Jeśli n jest liczbą złożoną, to istnieją podzielniki p i q:

obrazek

Rozważmy możliwe wartości tych podzielników:

obrazek

W takim przypadku drugi podzielnik q musi być mniejszy od pierwiastka z n, gdyż inaczej ich iloczyn byłby większy od n.
Podzielnik q znajdziemy zatem w przedziale od 2 do pierwiastka z n.

obrazek

Teraz drugi podzielnik q musi być większy od pierwiastka z n.
Podzielnik p znajdziemy w przedziale od 2 do pierwiastka z n.

obrazek

Podzielnik p lub q znajdziemy w przedziale od 2 do pierwiastka z n

Z rozważań tych wynika następujący wniosek:

Liczba n jest pierwsza, jeśli nie posiada podzielników w przedziale od 2 do pierwiastka z n.

Spostrzeżenie to pozwala znacznie zoptymalizować algorytm. Dotychczas, aby stwierdzić pierwszość liczby n o wartości w pobliżu miliona, program musiał wykonać milion dzieleń. Po modyfikacji dzieleń będzie tysiąc razy mniej. Modyfikacja funkcji isPrime() polegać będzie na wyliczeniu części całkowitej pierwiastka z n, a następnie zbadaniu podzielności liczby na przez liczby z przedziału od 2 do części całkowitej z pierwiastka z n.

Ulepszony algorytm sprawdzania pierwszości

Dane wejściowe:

n - liczby naturalna, której pierwszość badamy

Dane wyjściowe:

true - liczba n jest pierwsza
false - liczba n jest złożona

Dane pomocnicze:

i - kolejne podzielniki liczby n, i = 2, 3, ..., n-1
g - część całkowita pierwiastka z n

Lista kroków:

K01: Czytaj n
K02: g ← część całkowita pierwiastka z n
K03: Dla i = 2,3,...,g: jeśli n mod i = 0, to zakończ zwracając false
K04: Zakończ zwracając true

Program w języku C++:

Ćwiczenie na lekcji

Sprawdź czas generacji liczb pierwszych do 1000000 i porównaj go z czasem, który zanotowałeś dla poprzedniej wersji algorytmu. Wyciągnij odpowiednie wnioski.

Funkcję isPrime() można ulepszać dalej. Na przykład wszystkie liczby pierwsze za wyjątkiem 2 są nieparzyste. Zatem sprawdzamy, czy n jest równe 2. Jeśli tak, to zwracamy true i kończymy algorytm. W przeciwnym razie testujemy podzielność liczby n przez liczby nieparzyste z przedziału od 2 do pierwiastka z n. W ten sposób dodatkowo pozbędziemy się połowy dzieleń w porównaniu z poprzednią wersją algorytmu:

Ulepszony algorytm sprawdzania pierwszości

Dane wejściowe:

n - liczby naturalna, której pierwszość badamy

Dane wyjściowe:

true - liczba n jest pierwsza
false - liczba n jest złożona

Dane pomocnicze:

i - kolejne podzielniki liczby n, i = 2, 3, ..., n-1
g - część całkowita pierwiastka z n

Lista kroków:

K01: Czytaj n
K02: Jeśli n = 2, to zakończ zwracając true
K03: g ← część całkowita pierwiastka z n
K04: Dla i = 3,5,...,g : jeśli n mod i = 0, to zakończ zwracając false
K05: Zakończ zwracając true

Program w języku C++:

Ćwiczenie na lekcji

Zadania

Na podstawie podanego powyżej algorytmu zmodyfikuj odpowiednio programy:

testowania pierwszości
generacji liczb pierwszych w przedziale od 2 do n
generacji n liczb pierwszych.

Narysuj schematy blokowe dla obu ulepszonych funkcji isPrime().

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe