Prezentowane materiały są przeznaczone dla uczniów szkół ponadgimnazjalnych Autor artykułu: mgr Jerzy Wałaszek |
©2014 mgr
Jerzy Wałaszek
|
Liczby pierwsze można wyszukiwać poprzez eliminację ze zbioru liczbowego wszystkich wielokrotności wcześniejszych liczb.
Przykład:
Mamy następujący zbiór liczb naturalnych:
{2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50}
Ze zbioru wyrzucamy wszystkie wielokrotności pierwszej liczby 2. Otrzymujemy następujący zbiór:
{2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50}
W zbiorze pozostały liczby nieparzyste – z wyjątkiem pierwszej liczby 2. Liczby podzielne przez dwa zostały wyeliminowane. Teraz eliminujemy wielokrotności kolejnej liczby 3. Otrzymamy następujący zbiór:
{2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50}
Teraz w zbiorze pozostały liczby niepodzielne przez 2 i 3 – z wyjątkiem pierwszych 2 i 3. Zwróć uwagę, iż kolejna liczba 4 została już ze zbioru wyeliminowana. Skoro tak, to ze zbioru zniknęły również wszystkie wielokrotności liczby 4, ponieważ są one również wielokrotnościami liczby 2, a te wyeliminowaliśmy przecież na samym początku. Przechodzimy zatem do liczby 5 i eliminujemy jej wielokrotności otrzymując zbiór wynikowy:
{2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50}
Oprócz 2,3 i 5 pozostałe w zbiorze liczby nie dzielą się już przez 2,3 i 5. Liczba 6 jest wyeliminowana (wielokrotność 2), zatem przechodzimy do 7. Po wyeliminowaniu wielokrotności liczby 7 zbiór przyjmuje postać:
{2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50}
W zbiorze pozostały same liczby pierwsze.
{2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50}
Przy eliminacji wystarczy usunąć ze zbioru wielokrotności liczb leżących w przedziale od 2 do pierwiastka z n. Wyjaśnienie tego faktu jest identyczne jak w algorytmie szukania liczb pierwszych przez testowanie podzielności. Jeśli liczba p jest złożona, to musi posiadać czynniki pierwsze w przedziale od 2 do pierwiastka z p.
Powyższe operacje wyrzucania wielokrotności prowadzą do przesiania zbioru wejściowego. W zbiorze pozostają tylko liczby pierwsze, liczby będące wielokrotnościami poprzedzających je liczb zostają ze zbioru odsiane. Algorytm dokonujący tej eliminacji nosi nazwę sita Eratostenesa (ang. Eratosthenes' sieve) i jest jednym z najszybszych sposobów generowania liczb pierwszych.
Sito Eratostenesa (ang. the sieve of Eratosthenes) jest algorytmem dwuprzebiegowym. Najpierw dokonuje on eliminacji liczb złożonych ze zbioru zaznaczając je w określony sposób, a w drugim obiegu przegląda zbiór ponownie wyprowadzając na wyjście liczby, które nie zostały zaznaczone. Podstawowe znaczenie w tym algorytmie ma wybór odpowiedniej struktury danych do reprezentacji zbioru liczb. Na tym polu można dokonywać różnych optymalizacji. W pierwszym podejściu zastosujemy tablicę wartości logicznych T. Element T[i] będzie odpowiadał liczbie o wartości i. Zawartość T[i] będzie z kolei informowała o tym, czy liczba i pozostała w zbiorze (T[i] = true) lub została usunięta (T[i] = false).
Najpierw przygotowujemy tablicę reprezentującą zbiór liczbowy wypełniając ją wartościami logicznymi true. Odpowiada to umieszczeniu w zbiorze wszystkich liczb wchodzących w zakres od 2 do n. Następnie z tablicy będziemy usuwali kolejne wielokrotności początkowych liczb od 2 do pierwiastka całkowitego z n w pisując do odpowiednich elementów wartość logiczną false. Na koniec przeglądniemy zbiór i wypiszemy indeksy elementów zawierających wartość logiczną true – odpowiadają one liczbom, które w zbiorze pozostały.
Za pierwszą wielokrotność do wyrzucenia ze zbioru przyjmiemy kwadrat liczby i. Przyjrzyj się naszemu przykładowi. Gdy wyrzucamy wielokrotności liczby 2, to pierwszą z nich jest 4 = 22. Następnie dla wielokrotności liczby 3 pierwszą do wyrzucenia jest 9 = 32, gdyż 6 zostało wyrzucone wcześniej jako wielokrotność 2. Dla 5 będzie to 25 = 52, gdyż 10 i 20 to wielokrotności 2, a 15 jest wielokrotnością 3, itd. Pozwoli to wyeliminować zbędne obiegi pętli usuwającej wielokrotności.
n | – | liczba określająca górny kraniec przedziału poszukiwania liczb pierwszych, n N, n > 1 |
Kolejne liczby pierwsze w przedziale od 2 do n.
T | – | tablica wartości logicznych. T[i] {false,true}, dla i = 2,3,...,n. |
g | – | zawiera granicę wyznaczania wielokrotności. g N |
i | – | przebiega przez kolejne indeksy elementów T[i]. i N |
w | – | wielokrotności wyrzucane ze zbioru T, w N |
K01: | Dla i = 2,3,...,n wykonuj T[i] ← true | ; zbiór początkowo zawiera wszystkie liczby |
K02: | g ← [√n] | ; obliczamy granicę eliminowania wielokrotności |
K03: | Dla i = 2,3,...,g wykonuj kroki K04...K08 | ; w pętli wyrzucamy ze zbioru wielokrotności i |
K04: | Jeśli T[i] = false, to następny obieg pętli K03 | ; sprawdzamy, czy liczba i jest w zbiorze |
K05: | w ← i2 | ; jeśli tak, wyrzucamy jej wielokrotności |
K06: | Dopóki w ≤ n wykonuj kroki K07...K08 | ; ze zbioru |
K07: | T[w] ← false | |
K08: | w ← w + i | ; następna wielokrotność |
K09: | Dla i = 2,3,...,n wykonuj krok K10 | ; przeglądamy zbiór wynikowy |
K10: | Jeśli T[i] = true, to pisz i | ; wyprowadzając pozostałe w nim liczby |
K11: | Zakończ |
indeks | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 |
liczba | 3 | 5 | 7 | 9 | 11 | 13 | 15 | 17 | 19 | 21 | 23 | 25 | 27 | 29 | 31 | 33 | 35 | 37 | 39 | 41 | 43 | 45 | 47 | 49 | 51 | 53 | 55 | 57 | 59 | 61 | 63 | 65 | 67 | 69 | 71 | 73 | 75 | 77 | 79 | 81 |
Komórka o indeksie i oznacza liczbę o wartości 2i + 3. Np. komórka 7 reprezentuje liczbę 2x7 + 3 = 17.
Liczba o wartości k jest reprezentowana przez komórkę [k/2] - 1. Np. liczbę 45 reprezentuje komórka [45/2] - 1 = 21.
Z poprzedniego algorytmu pamiętamy, że pierwszą wyrzucaną wielokrotnością jest zawsze kwadrat liczby podstawowej. Nasza tablica rozpoczyna się od liczby 3, zatem pierwszą wielokrotnością, którą usuniemy, będzie liczba 9 na pozycji 4:
indeks | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 |
liczba | 3 | 5 | 7 | 9 | 11 | 13 | 15 | 17 | 19 | 21 | 23 | 25 | 27 | 29 | 31 | 33 | 35 | 37 | 39 | 41 | 43 | 45 | 47 | 49 | 51 | 53 | 55 | 57 | 59 | 61 | 63 | 65 | 67 | 69 | 71 | 73 | 75 | 77 | 79 | 81 |
Zauważ, że kolejne wielokrotności liczby 3, które są reprezentowane w tablicy, znajdują się w niej w odstępach co 3:
indeks | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 |
liczba | 3 | 5 | 7 | 9 | 11 | 13 | 15 | 17 | 19 | 21 | 23 | 25 | 27 | 29 | 31 | 33 | 35 | 37 | 39 | 41 | 43 | 45 | 47 | 49 | 51 | 53 | 55 | 57 | 59 | 61 | 63 | 65 | 67 | 69 | 71 | 73 | 75 | 77 | 79 | 81 |
Oznaczmy przez p odstępy pomiędzy wielokrotnościami, a przez q pozycję kwadratu liczby, której wielokrotności usuwamy z tablicy. Na początku mamy:
Po usunięciu tych wielokrotności tablica T nie będzie zawierała dalszych liczb podzielnych przez 3. Przejdźmy do kolejnej liczby, czyli do 5. Kwadrat 5 znajduje się na pozycji 11:
indeks | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 |
liczba | 3 | 5 | 7 | 9 | 11 | 13 | 15 | 17 | 19 | 21 | 23 | 25 | 27 | 29 | 31 | 33 | 35 | 37 | 39 | 41 | 43 | 45 | 47 | 49 | 51 | 53 | 55 | 57 | 59 | 61 | 63 | 65 | 67 | 69 | 71 | 73 | 75 | 77 | 79 | 81 |
Kolejne wielokrotności 5 znajdują się w naszej tablicy w odstępach co 5 (niektóre z nich są usunięte, ponieważ są również wielokrotnościami liczby 3) :
indeks | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 |
liczba | 3 | 5 | 7 | 9 | 11 | 13 | 15 | 17 | 19 | 21 | 23 | 25 | 27 | 29 | 31 | 33 | 35 | 37 | 39 | 41 | 43 | 45 | 47 | 49 | 51 | 53 | 55 | 57 | 59 | 61 | 63 | 65 | 67 | 69 | 71 | 73 | 75 | 77 | 79 | 81 |
Zapiszmy:
Następna liczba to 7 i jej pierwsza wielokrotność 49 na pozycji 23. Kolejne wielokrotności są w odstępach co 7:
indeks | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 |
liczba | 3 | 5 | 7 | 9 | 11 | 13 | 15 | 17 | 19 | 21 | 23 | 25 | 27 | 29 | 31 | 33 | 35 | 37 | 39 | 41 | 43 | 45 | 47 | 49 | 51 | 53 | 55 | 57 | 59 | 61 | 63 | 65 | 67 | 69 | 71 | 73 | 75 | 77 | 79 | 81 |
Znów zapiszmy:
Następna liczba to 9 i jej pierwsza wielokrotność 81 na pozycji 39. Kolejne wielokrotności są w odstępach co 9:
indeks | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 |
liczba | 3 | 5 | 7 | 9 | 11 | 13 | 15 | 17 | 19 | 21 | 23 | 25 | 27 | 29 | 31 | 33 | 35 | 37 | 39 | 41 | 43 | 45 | 47 | 49 | 51 | 53 | 55 | 57 | 59 | 61 | 63 | 65 | 67 | 69 | 71 | 73 | 75 | 77 | 79 | 81 |
Znów zapiszmy:
Wyrzucanie wielokrotności liczby 9 możemy pominąć, ponieważ sama liczba 9 jest już wyrzucona z tablicy przez 3. Ostatnią rozważaną tu liczbą jest 11 o kwadracie równym 121. Liczba 121 znajduje się na pozycji [121/2] - 1 = 59:
W tablicy ta pozycja już nie występuje (indeksy kończą się na wartości 39), zatem kończymy. W T pozostały jedynie liczby pierwsze. Na koniec wyprowadźmy wzory rekurencyjne dla kolejnych wartości p oraz q. W tym celu wystarczy zauważyć prostą zależność (dla dociekliwych - wynika ona z rozkładu kwadratów liczb nieparzystych na sumę różnic - patrz: całkowity pierwiastek kwadratowy):
i | pi | 2(pi-1) | qi |
0 | 3 | 3 | |
1 | 3+2 = 5 | 2x(5-1) = 8 | 3+8 = 11 |
2 | 5+2 = 7 | 2x(7-1) = 12 | 11+12 = 23 |
3 | 7+2 = 9 | 2x(9-1) = 16 | 23+16 = 39 |
4 | 9+2 = 11 | 2x(11-1) = 20 | 39+20 = 59 |
Zatem możemy zapisać wzór rekurencyjny:
Dla i > 0:
pi = pi-1
+ 2
qi = qi-1 + 2(pi
- 1)
Po tych rozważaniach przystępujemy do zapisu algorytmu.
n | – | liczba określająca górny kraniec przedziału poszukiwania liczb pierwszych, n N, n > 1 |
Kolejne liczby pierwsze w przedziale od 2 do n.
T | – | tablica wartości logicznych. |
i, k | – | przebiega przez indeksy T. i N |
p, q | – | odstęp wielokrotności oraz pierwsza wielokrotność, p,q N |
m | – | połowa z n, m N |
K01: | m ← n shr 1 | ; m to połowa z n |
K02: | Utwórz m elementową tablicę T i wypełnij ją wartościami true | ; w T są początkowo wszystkie liczby nieparzyste |
K03: | i ← 0 | ; indeks kolejnych liczb liczb pierwszych w T |
K04: | p ← 3; q ← 3 | ; odstęp 3, pierwsza wielokrotność 3 (9) |
K05: | Jeśli T[i] = false, to idź do K10 | ; przeskakujemy liczby wyrzucone z T |
K06: | k ← q | ; w k indeks pierwszej wielokrotności liczby 2i + 1 |
K07: | Dopóki k < m wykonuj kroki K08...K09 | ; wyrzucamy z T wielokrotności |
K08: | T[k] ← false | |
K09: | k ← k + p | ; wyznaczamy pozycję kolejnej wielokrotności, przesuniętą o odstęp p |
K10: | i ← i + 1 | ; indeks następnej liczby w T |
K11: | p ← p + 2 | ; zwiększamy odstęp wielokrotności |
K12: | q ← q + (p - 1) shl 1 | ; wyznaczamy pierwszą wielokrotność |
K13: | Jeśli q < m, to idź do K05 | |
K14: | Pisz 2 | ; pierwsza liczba pierwsza wyprowadzana bezwarunkowo |
K15: | Dla i = 0,1,...,m-1 wykonuj krok K16 | ; przeglądamy T wypisując pozostałe w niej liczby pierwsze |
K16: | Jeśli T[i] = true, to pisz 2i + 3 | |
K17: | Zakończ |
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