Serwis Edukacyjny w I-LO w Tarnowie ![]() Materiały dla uczniów liceum |
Autor artykułu: mgr Jerzy Wałaszek |
©2023 mgr Jerzy Wałaszek |
Na przykład, liczba 6 posiada 4 różne podzielniki: 1, 2, 3, 6. Liczba 4 nie jest podzielnikiem liczby 6, ponieważ:
Tak samo liczba 5 nie jest podzielnikiem liczby 6:
Liczba pierwsza (ang. primary number) jest
liczbą naturalną posiadającą dokładnie dwa różne podzielniki: 1 i
siebie samą.
|
Liczba 1 nie jest liczbą pierwszą, ponieważ ma tylko 1 podzielnik: 1, a nie dwa różne.
Liczba 2 jest początkową liczbą pierwszą, ma dokładnie dwa podzielniki różne: 1 i 2.
Liczba 3 ma dokładnie dwa podzielniki: 1 i 3, jest zatem pierwsza.
Liczba 4 nie jes liczbą pierwszą, ponieważ posiada 3 podzielniki: 1, 2 i 4.
Oto kilka początkowych liczb pierwszych:
2 3 5 7 11 13 17 19 23 29 31 37 41...
Ciąg liczb pierwszych jest nieskończony, czyli nie ma największej liczby pierwszej. Dowód pochodzi od Euklidesa i jest następujący:
Tworzymy liczbę Euklidesa E następująco:
Liczba Euklidesa E jest sumą iloczynu wszystkich liczb pierwszych ze zbioru P i liczby 1. W takiej postaci liczby E nie dzieli żadna z liczb pierwszych ze zbioru P, ponieważ przy podziale zawsze otrzymujemy resztę 1 (uzasadnij to).
Liczba E jest zatem:
Trzeciej możliwości nie ma. W każdym z tych dwóch przypadków otrzymujemy nową liczbę pierwszą niezawartą w zbiorze P, co przeczy założeniu, iż zbiór P zawiera wszystkie liczby pierwsze. Wynika stąd, iż zbiór liczb pierwszych jest zbiorem nieskończonym.
Aby sprawdzić, czy liczba p jest liczbą pierwszą, próbujemy ją dzielić przez kolejne liczby od 2 po p - 1. Jeśli żadna z tych liczb nie dzieli p, to p jest pierwsze. W przeciwnym razie p jest złożone.
Dane wyjściowe: prawda - liczba p jest pierwsza, fałsz - liczba p jest złożona
Lista kroków:
K01: Dla i = 2,3,...,p - 1, wykonuj krok K02
K02: Jeśli i dzieli p, to zakończ z
wynikiem fałsz
K03: Zakończ z wynikiem prawda
Kroki K01 i K02 tworzą pętlę, w której sprawdzana jest podzielność testowanej na pierwszość liczby p przez kolejne dzielniki od 2 do p - 1. Jeśli którykolwiek z nich dzieli p, to p nie jest liczbą pierwszą, ponieważ ma dzielnik różny od 1 i od siebie samej. W takim przypadku zwracamy fałsz i kończymy algorytm.
Gdy pętla sprawdzi wszystkie dzielniki od 2 do p - 1 i żaden nie dzieli p, to algorytm przechodzi do kroku K03, gdzie się kończy z wynikiem prawda, czyli p jest liczbą pierwszą.
Poniższy program wykorzystuje ten algorytm do wyznaczenia liczb pierwszych z przedziału [a,b] (a > 1; b ≥ a):
// Liczby pierwsze // Algorytm nr 1 //---------------- #include <iostream> using namespace std; // Zwraca: // true - p jest pierwsze // false - p jest złożone //------------------------ bool is_prime(unsigned p) { for(unsigned i = 2; i < p; i++) if(!(p % i)) return false; return true; } int main() { cout << "Wyszukiwanie liczb pierwszych" << endl << "w zakresie od a do b" << endl << "-----------------------------" << endl << endl; unsigned a, b; cout << "a = "; cin >> a; // Odczytujemy zakres cout << "b = "; cin >> b; // poszukiwania cout << endl; // Wypisujemy znalezione liczby pierwsze if((a > 1) && (b >= a)) for(unsigned p = a; p <= b; p++) if(is_prime(p)) cout << p << " "; cout << endl << endl; return 0; } |
Wyszukiwanie liczb pierwszych w zakresie od a do b ----------------------------- a = 100000000 b = 100000050 100000007 100000037 100000039 100000049 |
Zwróć uwagę, że im większe liczby, tym dłużej je komputer wyszukuje. Spowodowane to jest tym, iż liczba pierwsza zostaje rozpoznana po wykonaniu wszystkich dzieleń próbnych od 2 do p - 1, a ich liczba rośnie wraz ze wzrostem p.
Ponieważ będziemy ten algorytm stopniowo poprawiać, zmodyfikujemy nieco program tak, aby wyszukiwał liczby pierwsze w zakresie od 1000000000 do 1000000200:
// Liczby pierwsze // Algorytm nr 1 //---------------- #include <iostream> using namespace std; // Zwraca: // true - p jest pierwsze // false - p jest złożone //------------------------ bool is_prime(unsigned p) { for(unsigned i = 2; i < p; i++) if(!(p % i)) return false; return true; } int main() { unsigned const A = 1000000000; unsigned const B = 1000000200; // Wypisujemy znalezione liczby pierwsze for(unsigned p = A; p <= B; p++) if(is_prime(p)) cout << p << " "; cout << endl << endl; return 0; } |
Uruchom program trzykrotnie i zapisz czasy obliczeń, które są podawane w oknie konsoli przy zakończeniu programu. Za każdym razem czasy będą się nieco różnić, ponieważ w tle komputer wykonuje również procedury systemowe i te zadania nieco opóźniają nasz program. Z tych 3 czasów wybierz najmniejszy. Otrzymasz przybliżony czas wyszukiwania liczb pierwszych w przedziale [1000000000, 1000000200] na swoim komputerze. U mnie czas ten wyniósł: 41,276 s.
Uruchomienie | Czas |
#1 | 41,314 s |
#2 | 41,276 s |
#3 | 41,286 s |
Ulepszanie algorytmu będzie polegało na eliminacji liczby dzieleń, ponieważ ich jest najwięcej przy dużych liczbach i wpływają one bezpośrednio na czas obliczeń. Najpierw usuniemy dzielniki parzyste. Jedyną liczbą pierwszą parzystą jest liczba 2. Zatem algorytm powinien sprawdzić, czy testowana liczba jest równa 2. Jeśli tak, to algorytm kończy działanie z wynikiem prawda. Jeśli liczba nie jest równa 2, to sprawdzamy, czy dzieli się przez 2. Jeśli tak, to nie jest pierwsza, ponieważ jest różna od 2, a 2 jest jedyną liczbą pierwszą podzielną przez 2, a tę już wyeliminowaliśmy. W tym przypadku algorytm kończy pracę z wynikiem fałsz. Jeśli liczba nie dzieli się przez 2, to również nie dzieli się przez 4, 6, 8, ... ,czyli przez liczby parzyste. Pozostaje nam zatem sprawdzenie podziału przez liczby nieparzyste. W ten sposób zredukowaliśmy liczbę podzielników o połowę.
Dane wyjściowe: prawda - liczba p jest pierwsza, fałsz - liczba p jest złożona
Lista kroków:
K01: Jeśli p = 2, to zakończ z wynikiem prawda
K02: Jeśli p dzieli się przez 2, to zakończ z wynikiem
fałsz
K03: i ← 3
K04: Dopóki i < p wykonuj kroki K05 ... K06
K05: Jeśli p dzieli się przez i, to
zakończ z wynikiem fałsz
K06: i ← i + 2
K07: Zakończ z wynikiem prawda
// Liczby pierwsze // Algorytm nr 2 //---------------- #include <iostream> using namespace std; // Zwraca: // true - p jest pierwsze // false - p jest złożone //------------------------ bool is_prime(unsigned p) { if(p == 2) return true; if(!(p % 2)) return false; for(unsigned i = 3; i < p; i += 2) if(!(p % i)) return false; return true; } int main() { unsigned const A = 1000000000; unsigned const B = 1000000200; // Wypisujemy znalezione liczby pierwsze for(unsigned p = A; p <= B; p++) if(is_prime(p)) cout << p << " "; cout << endl << endl; return 0; } |
Uruchom program 3 razy i zapisz czasy działania. Z tych 3 czasów wybierz najmniejszy.
Uruchomienie | Czas |
#1 | 20,648 s |
#2 | 20,637 s |
#3 | 20,612 s |
U mnie czas wyniósł 20,612 s. Poprzedni czas był równy 41,276 s. Jak widzisz ulepszony algorytm wykonuje się o połowę krócej (ponieważ zredukowaliśmy o połowę liczbę dzieleń). W informatyce jest zwykle tak, iż proste algorytmy mają długi czas rozwiązywania problemu, natomiast algorytmy skomplikowane wykonują się szybciej.
Trzeci algorytm musi sięgnąć do matematyki, aby jeszcze bardziej zredukować liczbę wykonywanych dzieleń.
Jeśli liczba p jest liczbą złożoną (czyli nie jest pierwsza), to można ją przedstawić jako iloczyn dwóch liczb naturalnych będących jej dzielnikami różnymi od 1 i od niej samej:
Zastanówmy się, jakie wartości mogą te dzielniki przyjmować. Mamy dwa możliwe przypadki:
Jeśli wykluczymy dzielnik 2, to liczba p jest pierwsza, jeśli nie posiada dzielnika nieparzystego w przedziale od 3 do pierwiastka kwadratowego z p. Nie trzeba zatem przeszukiwać całego przedziału od 3 do p -1 w poszukiwaniu dzielnika. Jaka stąd korzyść? Dla liczby z zakresu miliona algorytm nr 2 musiał wykonać około pół miliona dzieleń, aby potwierdzić jej pierwszość. Teraz tych dzieleń jest około pierwiastek kwadratowy z miliona przez 2, czyli około 500 (2 tysiące razy mniej)!
Dane wyjściowe: prawda - liczba p jest pierwsza, fałsz - liczba p jest złożona
Lista kroków:
K01: Jeśli p = 2, to zakończ z wynikiem prawda
K02: Jeśli p dzieli się przez 2, to zakończ z wynikiem
fałsz
K03: g ← pierwiastek z p
K04: i = 3
K05: Dopóki i ≤ g wykonuj kroki K06
... K07
K06: Jeśli p dzieli się przez i, to
zakończ z wynikiem fałsz
K07: i ← i + 2
K08: Zakończ z wynikiem prawda
// Liczby pierwsze // Algorytm nr 3 //---------------- #include <iostream> #include <cmath> using namespace std; // Zwraca: // true - p jest pierwsze // false - p jest złożone //------------------------ bool is_prime(unsigned p) { if(p == 2) return true; if(!(p % 2)) return false; unsigned g = sqrt(p); for(unsigned i = 3; i <= g; i += 2) if(!(p % i)) return false; return true; } int main() { unsigned const A = 1000000000; unsigned const B = 1000000200; // Wypisujemy znalezione liczby pierwsze for(unsigned p = A; p <= B; p++) if(is_prime(p)) cout << p << " "; cout << endl << endl; return 0; } |
Do programu dołączyliśmy plik nagłówkowy cmath, w którym znajdują się definicje funkcji matematycznych - potrzebujemy funkcji pierwiastka kwadratowego – sqrt( ).
Program uruchom 3 razy, zanotuj czasy wykonań i wybierz najmniejszy.
Uruchomienie | Czas |
#1 | 0,037 s |
#2 | 0,032 s |
#3 | 0,022 s |
U mnie czas wyniósł 0,022 sekundy, czyli praktycznie natychmiast.
Podsumujmy czasy wykonań:
Algorytm | Czas wykonania | Porównanie |
#1 | 40,046 s | Najwolniejszy |
#2 | 20,612 s | |
#3 | 0,022 s | Najszybszy |
Istnieją jeszcze szybsze metody sprawdzania pierwszości liczby, które znajdują zastosowanie dla naprawdę dużych liczb.
![]() |
Zespół Przedmiotowy Chemii-Fizyki-Informatyki w I Liceum Ogólnokształcącym im. Kazimierza Brodzińskiego w Tarnowie ul. Piłsudskiego 4 ©2023 mgr Jerzy Wałaszek |
Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.