Liczby pierwsze

27.11.2009
Trudność

Analizując złożoność sita Erastotenesa, natrafiliśmy na dość częstego bohatera: liczby harmoniczne:

$$H_k = \sum _ {i=1} k \frac {1}{i} $$
Powiedzieliśmy sobie, że zachodzi $ H_n \in \Theta(\lg n) $, co da się pokazać prosto dla n będących potęgami dwójki, a następnie dla pozostałych korzystając z tego że $ H_n $ jest monotoniczną funkcją $ n $:

$$H_{2^k} = 1 + 1/2 + 1/3 + 1/4 + ... + 1/{2^k} =$$
$$ = 1 + \frac 1 2+ (\frac 1 3+ \frac 1 4) + (\frac 1 5+ \frac 1 6+\frac 1 7+\frac 1 8) + ... + (...+\frac 1 {2^k}) =$$
$$ \leq 1 + 1*1 + 2*\frac 1 2 + 4*\frac 1 4 + ...+ {2^k}*\frac 1 {2^k}$$
$$ = 1+k$$

oraz

$$H_{2^k} = 1 + 1/2 + 1/3 + 1/4 + ... + 1/{2^k} =$$
$$ = 1 + 1/2+ (1/3+1/4) + (1/5+1/6+1/7+1/8) + ... + (...+1/{2^k}) =$$
$$ \ge 1 + 1/2 + 2*1/4 + 4*1/8 + ...+ {2^{k-1}}*1/{2^k}$$
$$ = 1+k/2$$

Powiedzieliśmy sobie o kilku możliwych optymalizacjach:

  • użycie vector pozwala zmniejszyć zużycie pamięci (kosztem prędkości)
  • pomijanie liczb parzystych pozwala zmniejszyć czas i pamięć
  • zaczynanie skreślania od kwadratu liczby pierwszej, nieco skraca czas (dlaczego niewiele?)

Próbowałem też wyjaśnić jak pomysł z przeskakiwaniem liczb parzystych rozszerzyć, na kolejne liczby pierwsze. Na początek pogadaliśmy trochę o Chińskim Twierdzeniu o Resztach, które (w dość niekonstruktywny sposób) mówi tyle, że jeśli mamy kilka liczb (względnie) pierwszych, to każda kombinacja reszt z dzielenia przez nie zdarza się dokładnie jeden raz wśród liczb naturalnych mniejszych od ich iloczynu. Po prawdzie, zdarza się dokładnie raz w każdym przedziale o tej długości.

Ciekawym zadaniem jest wcielenie się w generała który ryzykując głową przed Cesarzem musi mu zdać raport na temat liczby żołnierzy. O tym jak na podstawie reszt skonstruować liczbę, która ma takie reszty, na razie sobie nie mówiliśmy, ale podpowiem, że przydatne jest do tego liczenie odwrotności.

Jednym z wniosków z tego twierdzenia jest fakt, że jeśli skreślimy liczby parzyste, podzielne przez 3 oraz podzielne przez 5, to pozostanie nam 1/2* 2/3 * 4/5 wszystkich liczb. Ogólnie jeśli użyjemy liczb pierwszych $ p_1,\ldots,p_k $, to pozostanie nam $ \prod _ {i=1} ^ {k}  1- \frac {1} {p_i} $ wszystkich liczb spośród tych mniejszych od $ \prod  _ {i=1} ^ {k} p_i $. Po prawdzie działa to dla każdego przedziału o tej długości.

Prowadzi to mniej więcej do takiego algorytmu znajdującego wszystkie liczby pierwsze mniejsze od n.

  1. Weź kilka małych lizczb pierwszych $ p_1,\ldots,p_k $
  2. Niech $ m=\prod  _ {i=1} ^ {k} p_i $
  3. Niech $ g=\prod _ {i=1} ^ {k}  p_i -1 $
  4. Znajdź wszystkie $ g $ liczb z zakresu $ [0,m) $, które nie dzielą się przez żadną z liczb $ p_1,\ldots,p_k $ i zapisz w tablicy pomocniczej int T[g]
  5. Dla każdego $ i=0,\ldots, \lfloor n/m \rfloor $
    1. Dla każdego $ j=0,\ldots,g-1 $
      1. Jeśli $ p=i*m+T[j] $ jest mniejsze od n i nie jest skreślone, to wypisz $ p $ i skreśl jego wielokrotności

Tutaj może jeszcze taka uwaga, że to skreślanie wielokrotności $ p $ również można robić sprytniej, próbując skakać tylko po liczbach postaci $ (1+i*m+T[j])*p $

Co nam to wszystko daje? W sumie to nie wiem, bo nie próbowałem i zachęcam do eksperymentów. Eksperymentujac warto porównywać wyniki z programem wzorcowym. Teoretycznie można liczyć, że w każdej pętli wykonamy tylko $ (g/m) $ iteracji w porównaniu do oryginalnego algorytmu. Zarówno w tej zewnętrznej (szukającej liczb pierwszych) jak i tej wewnętrznej (skreślającej jej wielokrotności). Wydawać by się zatem mogło, że łączne przyspieszenie to $ (g/m)^2 $, ale oczywiście tak nie jest (dlaczego?).

Tak czy owak powinno nam zależeć, aby stosunek $ g/m $ był jak najmniejszy. Wynosi on $ \prod _ {i=1} ^ {k}  1- \frac {1} {p_i} $, więc im więcej liczb pierwszych i im mniejsze one są, tym lepiej dla nas. Niestety wszystko to ma sens tylko wtedy, gdy $ g $, a więc rozmiar tablicy T, jest na tyle mały, by tablicę T można było zhardcodować w pliku źródłowym. Na pewno nie możemy ich wziąć więcej niż $ \lg n $.

0
Twoja ocena: Brak

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com