![]() |
![]() ![]() ![]() ![]()
Autor artykułu: mgr Jerzy Wałaszek, wersja 1.0 |
©2008 mgr
Jerzy Wałaszek |
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, ∞).
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 = {p1, p2, p3, ..., pn-1, pn}, gdzie pi, 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 = p1 × p2 × p3 × ... × pn-1 × pn + 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 pk, 1 ≤ k ≤ n, należącej do zbioru P mamy:
Ułamek 1 / pk 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.
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.
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:
Program w języku C++:
Ćwiczenie na lekcji
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.
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:
Program w języku C++:
Ćwiczenie na lekcji
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:
Program w języku C++:
Ćwiczenie na lekcji
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:
Rozważmy możliwe wartości tych podzielników:
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.
Teraz drugi podzielnik q musi być większy
od pierwiastka z n.
Podzielnik p znajdziemy w przedziale od 2 do pierwiastka
z n.
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.
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:
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
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().
![]() | I Liceum Ogólnokształcące |
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