Serwis Edukacyjny w I-LO w Tarnowie Materiały dla uczniów liceum |
Wyjście Spis treści Wstecz Dalej
Autor artykułu: mgr Jerzy Wałaszek |
©2024 mgr Jerzy Wałaszek |
Liczba 1 nie jest pierwszą, ponieważ dzieli się tylko przez 1, a nie posiada drugiego podzielnika różnego od 1. Przykłady liczb pierwszych:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 ...
Liczby pierwsze mają ogromne znaczenie we współczesnej informatyce. Na nich opierają się zaawansowane systemy szyfrujące używane przez banki, służby państwowe i wojsko. Dlatego umiejętność sprawdzania pierwszości liczby oraz generacji liczb pierwszych jest podstawową umiejętnością każdego informatyka.
Załóżmy, że zbiór liczb pierwszych P jest zbiorem skończonym i zawiera n różnych liczb pierwszych:
Euklides tworzy liczbę E (zwaną liczbą Euklidesa) wg następującego wzoru:
Liczby E nie dzieli żadna z liczb należących do zbioru P - zawsze zostanie reszta 1:
Dzieje się tak dlatego, że liczba E jest sumą dwóch składników - iloczynu wszystkich liczb pierwszych ze zbioru P oraz 1. Iloczyn jest podzielny przez swój dowolny składnik. Wynikiem jest iloczyn liczb ze zbioru P, w którym brak tego składnika. Natomiast 1 nie dzieli się przez żadną z tych liczb i zostaje jako reszta.
Wynikają z tego dwa wnioski:
Trzeciej możliwości nie ma. W obu możliwych przypadkach dostajemy nową liczbę pierwszą, której zbiór P nie zawiera. Przeczy to założeniu, że zbiór P zawierał wszystkie liczby pierwsze. Skoro tak, to zbiór liczb pierwszych nie może być zbiorem skończonym.
Liczba pierwsza p, p > 2, jest liczbą niepodzielną przez żadną z liczb należących do przedziału od 2 do p-1.
Ta druga definicja daje nam wskazówkę, jak szukać liczb pierwszych. Dla danej liczby p wystarczy sprawdzić, czy dzieli się bez reszty przez jakąś liczbę z przedziału od 2 do p-1. Jeśli tak, to p nie jest liczbą pierwszą. Jeśli żadna z liczb z przedziału od 2 do p-1 nie dzieli liczby p, p jest liczba pierwszą.
Wejście:
p - sprawdzana liczba naturalna
Wyjście:
t = true, liczba p jest liczbą pierwszą
t = false, liczba p nie jest liczbą pierwszą
Zmienne pomocnicze:
i - kolejne dzielniki naturalne dla liczby p
K01: | t ← true | ; zakładamy sukces |
K02: | Dla i = 2,3,...,p-1: wykonuj K03 | ; dzielniki |
K03: | Jeśli p dzieli się przez
i,
to t ← false Zakończ |
; sprawdzamy podzielność i jeśli występuje, ; to zerujemy t i kończymy |
K04: | Zakończ | ; zakończenie po wyjściu z pętli |
Na podstawie powyższego algorytmu napisz program w języku C++, który wygeneruje n kolejnych liczb pierwszych.
Podany powyżej algorytm, chociaż poprawnie działa, nie jest zbytnio efektywny. Aby stwierdzić, czy liczba p jest pierwsza, musi on wykonać (p - 3) dzieleń próbnych. Jeśli p jest duże, to liczba dzieleń jest równie duża. Wykonanie algorytmu zajmuje długi czas. Zastanówmy się, czy nie możemy go ulepszyć.
Jeśli liczba p jest liczbą złożoną (a zatem nie jest liczbą pierwszą), to można ją zapisać w postaci iloczynu dwóch liczb naturalnych a i b, które obie są różne od liczby p:
Z tych dwóch liczb a i b wystarczy znaleźć tylko jedną, aby wykluczyć pierwszość liczby p. Mamy dwa możliwe przypadki:
Widzimy, że w obu przypadkach jeden z dzielników występuje w przedziale od 2 do pierwiastka z p. Nie może się tak zdarzyć, że oba dzielniki a i b są większe od pierwiastka z p, gdyż wtedy ich iloczyn byłby większy od p. Zatem w celu znalezienia możliwego dzielnika wystarczy przeszukać przedział od 2 do pierwiastka z p. To bardzo duże usprawnienie. Poprzednio, aby sprawdzić, czy liczba p równa w przybliżeniu milion jest liczbą pierwszą, należało wykonać około miliona dzieleń. Teraz tych dzieleń jest tylko tysiąc - czyli tysiąc razy mniej. Im większa liczba p, tym zysk mamy większy. Jeśli same liczby a i b są złożone, to nic nie szkodzi - wtedy ich dzielniki są od nich mniejsze i tym bardziej wpadają w nasz przedział: jeśli p dzieli się przez jakąś liczbę a, to p dzieli się również przez wszystkie dzielniki liczby a. Jest to bardzo proste do udowodnienia. Wystarczy zatem znaleźć pierwszy z takich dzielników, aby wykluczyć pierwszość liczby p.
Wejście:
p - sprawdzana liczba naturalna
Wyjście:
t = true, liczba p jest liczbą pierwszą
t = false, liczba p nie jest liczbą pierwszą
Zmienne pomocnicze:
g - pierwiastek całkowity z p
i - kolejne dzielniki naturalne dla liczby p
K01: | t ← true | ; zakładamy sukces |
K02: | g ← |√p| | ; obliczamy pierwiastek całkowity z p |
K03: | Dla i = 2,3,...,g: wykonuj K04 | ; dzielniki |
K04: | Jeśli p dzieli się przez
i,
to t ← false Zakończ |
; sprawdzamy podzielność i jeśli występuje, ; to zerujemy t i kończymy |
K05: | Zakończ | ; zakończenie po wyjściu z pętli |
Kolejne przyspieszenie pracy algorytmu uzyskamy ograniczając dalej podzielniki. Na początku algorytmu sprawdzamy, czy badana liczba jest podzielna przez 2. Jeśli tak, to nie jest pierwsza. Jeśli nie, to możemy dalej wyeliminować podzielniki parzyste. Zredukuje nam to ich liczbę o połowę. Badane liczby p muszą być większe od 2. Liczba 2 jest jedyną liczbą pierwszą podzielną przez 2.
Wejście:
p - sprawdzana liczba naturalna, p > 2
Wyjście:
t = true, liczba p jest liczbą pierwszą
t = false, liczba p nie jest liczbą pierwszą
Zmienne pomocnicze:
g - pierwiastek całkowity z p
i - kolejne dzielniki nieparzyste dla liczby p
K01: | t ← true | ; zakładamy sukces |
K02: | Jeśli p = 2, to zakończ | ; jedyna liczba pierwsza parzysta |
K03: | Jeśli p dzieli się przez 2, to t ← false Zakończ |
; eliminujemy pozostałe liczby parzyste |
K04: | g ← |√p| | ; granica podzielników |
K05: | Dla i = 3,5,7...,g: wykonuj K06 | ; podzielniki nieparzyste |
K06: | Jeśli p dzieli się przez
i,
to t ← false Zakończ |
|
K07: | Zakończ | ; zakończenie po wyjściu z pętli |
Zespół Przedmiotowy Chemii-Fizyki-Informatyki w I Liceum Ogólnokształcącym im. Kazimierza Brodzińskiego w Tarnowie ul. Piłsudskiego 4 ©2024 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:
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.