Omówienie zadania Suma liczb pierwszych (III etap XXVIII OI)

Dla danej liczby całkowitej \(n\) mamy wyznaczyć spójny przedział w ciągu liczb pierwszych, którego sumą jest \(n\).

Podzadanie 1

Chyba najprostsze rozwiązanie tego zadania sprowadza się do przejrzenia wszystkich przedziałów, posumowania liczb pierwszych w każdym z nich i wypisania jednego z przedziałów, dla którego ta suma była równa \(n\).

Tak więc musimy przeiterować się po wszystkich możliwych lewych końcach przedziału oraz po prawych końcach przedziału, a następnie dla każdego takiego wyboru przeiterować się po wszystkich liczbach w tym przedziale i zsumować tylko te, które są pierwsze.

Na początek przydałoby się znaleźć jakieś ograniczenie na końce przedziału, w którym będziemy sprawdzać. Nie jest to jednak trudne i nawet mamy podpowiedź w sekcji Wyjście, a mianowicie prawy koniec przedziału nie będzie większy niż \(n\). Jest to dość oczywiste, bo gdyby przedział zawierał jakąś liczbę pierwszą większą od \(n\), to jego suma automatycznie byłaby większa od \(n\), więc na pewno nie byłby dobrym przedziałem.

Tak więc złożoność czasową naszego rozwiązania możemy oszacować przez \(O(n^3)\) (ponieważ sprawdzamy \(O(n^2)\) różnych przedziałów i przeglądamy wszystkie \(O(n)\) liczb z danego przedziału), razy czas potrzebny na sprawdzenie, czy liczba jest pierwsza. Ponieważ \(n \leq 10^{11}\), jest to rozwiązanie zdecydowanie zbyt wolne. Zastanówmy się więc na początek, jak zmniejszyć koszt iterowania się po przedziałach, a następnie przyjrzymy się, jaki będzie koszt testowania pierwszości.

Zauważmy, że w tym naszym rozwiązaniu brutalnym wielokrotnie wykonujemy tę samą pracę: jeżeli mamy policzoną sumę dla jakiegoś przedziału \([l,r]\), to aby policzyć sumę dla przedziału \([l,r + 1]\), wystarczy wziąć poprzednią sumę i jeżeli \(r + 1\) jest liczbą pierwszą, to zwiększyć ją o \(r + 1\). To powoduje, że dla ustalonego lewego końca przedziału wystarczy przeiterować się kolejno po prawych końcach przedziałów i dla każdego z nich wykonywać jeden test pierwszości i uaktualniać sumę. To powoduje zmniejszenie złożoności na iteracje po przedziałach z \(O(n^3)\) na \(O(n^2)\).

Przyjrzyjmy się, jakie sumy przedziałów uzyskujemy dla ustalonej wartości \(l\). Ciąg tych sum jest niemalejący: do pewnego momentu będą one mniejsze od \(n\), potem być może na pewnym przedziale będą równe \(n\), ale od pewnego miejsca będą już ciągle większe od \(n\). Oznaczmy sobie przez \(r(l)\) taki najmniejszy koniec, że suma przedziału \([l,r(l)]\) jest co najmniej równa \(n\).

Zauważmy, że przy takiej definicji \(r(l + 1) \geq r(l)\). Tak więc, żeby znaleźć wartości \(r(l)\) dla wszystkich początków \(l\) możemy zastosować metodę gąsienicy, inaczej zwaną metodą dwóch wskaźników. Będziemy trzymać dwa wskaźniki: lewy pokazujący wartość \(l\) oraz prawy pokazujący wartość \(r(l)\) oraz sumę liczb pierwszych na przedziale pomiędzy tymi dwoma wskaźnikami. Za każdym razem, gdy przesuniemy wskaźnik lewy o jedną pozycję w prawo, uaktualniamy sumę, jeżeli poprzednia wartość wskazywana przez wskaźnik była liczbą pierwszą, a następnie przesuwamy prawy wskaźnik w prawo tak długo, jak suma liczb w przedziale jest mniejsza od \(n\). Ponieważ zarówno lewy, jak i prawy wskaźnik poruszają się jedynie w prawo, każdy z nich wykona \(O(n)\) kroków.

Tak więc sumaryczny koszt to będzie \(O(n)\) razy testowanie pierwszości. Naszą odpowiedzią będzie oczywiście jeden z przedziałów postaci \([l,r(l)]\), taki, dla którego suma będzie równa \(n\).

Mamy już całkiem niezłą złożoność związaną z iterowaniem po przedziałach. Zobaczmy zatem, w jakiej złożoności czasowej możemy wykonywać test pierwszości. Dla ustalanej liczby \(x\) ten test może polegać na systematycznym szukaniu jej dzielnika.

W tym celu możemy spróbować podzielić ją przez wszystkie liczby \(d\) mniejsze od \(x\), co da nam złożoność \(O(x)\), albo zauważyć, że w liczbie złożonej co najmniej jeden dzielnik musi być nie większy niż \(\sqrt{x}\) i próbować dzielić \(x\) przez wszystkie liczby nie większe niż \(\sqrt{x}\). To nam da oczywiście złożoność \(O(\sqrt{x})\). Jeżeli zastosujemy ten drugi test w naszym rozwiązaniu, dostaniemy ogólną złożoność \(O(n^{3/2})\).

Podzadanie 2 (sito Eratostenesa)

Wykorzystamy tutaj inną standardową metodę sprawdzania pierwszości, a mianowicie sito Eratostenesa, dzięki któremu stworzymy dużą tablicę, która na pozycji \(x\) będzie zawierała \(0\) lub \(1\), w zależności od tego, czy \(x\) jest liczbą pierwszą, czy nie. Dzięki temu, po takich obliczeniach wstępnych, test pierwszości będziemy mogli wykonać w czasie stałym.

W metodzie tej w początkowo pustej tabelce będziemy wykreślać wielokrotności kolejnych liczb pierwszych. Dla liczby pierwszej \(p\) wykreślamy z tabelki jej wielokrotności, zaczynając od \(p^2\) (bo jej wielokrotności \(kp\) dla \(k<p\) były wykreślone przy wykreślaniu któregoś z czynnika pierwszego liczby \(k\)). Zatem wystarczy ograniczyć się do tych liczb pierwszych, które są nie większe niż \(\sqrt{n}\). Złożoność sita Eratostenesa to \(O(n \log\log n)\).

Warto jeszcze sprawdzić, czy nasza tabelka zmieści się w dostępnym limicie pamięci. Dla \(n \leq 10^{8}\) będzie ona zawierać 96 MB jako tablica zmiennych bool albo 12 MB jako bitset. Wobec tego spokojnie zmieści się w limicie pamięci dla tego zadania wynoszącym 256 MB.

Pełne rozwiązanie (sito segmentowe)

Do rozwiązania zadania w całej ogólności wykorzystamy naszą implementację do podzadania, w którym \(n\) było nie większe niż \(10^{8}\). Albowiem nawet w przypadku \(n\) rzędu \(10^{11}\) może zdarzyć się tak, że istnieje przedział o prawym końcu mniejszym równym niż \(10^{8}\), w którym suma liczb pierwszych jest równa \(n\). W takim przypadku ten przedział zostanie znaleziony przez algorytm gąsienicy przeglądający liczby do \(10^{8}\).

Tak więc pozostaje nam rozprawić się z przedziałami, które zawierają jakąś liczbę pierwszą większą niż \(10^{8}\). W tym jednak przypadku kluczowa obserwacja jest taka, że takie przedziały nie mogą być zbyt długie. Gdyby zawierały same liczby większe niż \(10^{8}\), to nie może być ich więcej niż \(\frac{n}{10^{8}}\), czyli co najwyżej \(1000\). Musimy jednak też uwzględnić przypadek, w którym lewy koniec przedziału będzie mniejszy niż \(10^{8}\), to znaczy część liczb pierwszych będzie mniejsza niż \(10^{8}\), ale tylko nieznacznie, wobec tego w takiej sytuacji będziemy mieli w przedziale tysiąc kilka liczb.

Skoro więc liczba liczb pierwszych w przedziale jest dość mocno ograniczona, pomysł jest następujący: przeiterujmy się po tej liczbie. Załóżmy zatem, że nasz przedział zawiera \(k\) kolejnych liczb pierwszych i zastanówmy się, gdzie szukać takiego przedziału. Skoro jego suma to \(n\) i zawiera on \(k\) składników podobnego rzędu, wszystkie składniki powinny być zbliżone do średniej wartości składnika, to znaczy \(\frac{n}{k}\). A mówiąc konkretniej, wystarczy, że przedziału o sumie równej \(n\) poszukamy wśród \(k\) składników mniejszych równych od \(\frac{n}{k}\) oraz \(k\) składników większych równych niż \(\frac{n}{k}\).

To wystarczy, bo gdybyśmy chcieli rozważyć jakikolwiek mniejszy składnik, to przedział długości \(k\) zawierający ten składnik musiałby mieć sumę mniejszą od \(n\), natomiast jakikolwiek przedział długości \(k\) zawierający większy składnik musiałby mieć sumę większą niż \(n\). Zatem, jeżeli uda nam się znaleźć \(k\) liczb pierwszych mniejszych od \(\frac{n}{k}\) i \(k\) liczb pierwszych większych niż \(\frac{n}{k}\), to na ich zbiorze możemy uruchomić algorytm gąsienicy w poszukiwaniu sumy równej \(n\). Pytanie jest zatem, jak długie kawałki wokół \(\frac{n}{k}\) musimy rozważyć, żeby znaleźć w nich po \(k\) liczb pierwszych, oraz jak szybko sprawdzać pierwszość liczb w tych kawałkach.

Wiemy, że liczby pierwsze są rozłożone dość gęsto wśród liczb naturalnych. A konkretnie, liczba liczb pierwszych w przedziale od \(1\) do \(n\) jest rzędu \(\frac{n}{\log n}\). Możemy zatem się spodziewać, że długości kawałków, które musimy rozważyć, będą rzędu \(k \cdot \log n\). Jednak wyznaczenie konkretnego ograniczenia na długość kawałka może być nieco problematyczne, więc poradzimy sobie bez wyznaczania takiego ograniczenia. Zacznijmy od kawałka pewnej długości \(d\), początkowo równej na przykład \(k \log n\), a następnie sprawdzimy, ile liczb pierwszych znajduje się w tym kawałku.

Jeżeli będzie ich co najmniej \(k\), to kończymy. W przeciwnym wypadku zwiększamy długość rozpatrywanego kawałka do \(2d\) i powtarzamy całą operację od początku. Zauważmy, że za każdym razem w przypadku porażki będziemy zwiększać długość rozpatrywanego kawałka razy \(2\). Wobec tego sumaryczny koszt sprawdzeń na wszystkich krótszych kawałkach będzie zamortyzowany kosztem sprawdzenia na kawałku najdłuższym. Tak więc będzie to złożoność sprawdzania liczb pierwszych na kawałku długości rzędu \(O(k \log n)\).

Pozostaje nam odpowiedź na pytanie, jak szybko sprawdzać pierwszość liczb na pewnym przedziale od \(l\) do \(r\), gdzie \(r\) może być rzędu \(n\), natomiast ograniczona jest długość przedziału będąca rzędu \(r-l = O(k \log n)\). Do tego wykorzystamy uogólnienie sita Eratostenesa, zwane pod nazwą sito segmentowe.

Przypomnijmy sobie, że w sicie Eratostenesa do wyznaczania liczb pierwszych z przedziału od \(2\) do \(n\) wystarczyło, że wykreśliliśmy liczby pierwsze nie większe niż \(\sqrt{n}\). Pomysł więc będzie następujący. Najpierw wykonamy sito Eratostenesa, ale na przedziale od \(2\) do \(\sqrt{n}\). To pozwoli nam znaleźć wszystkie liczby pierwsze nie większe niż \(\sqrt{n}\). Następnie, jeżeli będziemy chcieli znaleźć liczby pierwsze w dowolnym przedziale od \(l\) do \(r\), gdzie \(r\) jest mniejsze lub równe od \(n\), to wystarczy, że wykreślimy wielokrotności liczb pierwszych nie większych niż \(\sqrt{n}\) na tym właśnie przedziale. Dla każdej liczby pierwszej \(p \leq \sqrt{n}\) zaczynamy zawsze od pierwszej wielokrotności większej lub równej od \(l\). Wszystkie niewykreślone liczby są to liczby pierwsze w przedziale od \(l\) do \(r\).

Złożoność szukania liczb pierwszych na takim przedziale jest równa \(O(\frac{\sqrt{r}}{\log r}) + (r-l) \log\log r)\). Ta złożoność będzie wystarczająca, żeby znaleźć kawałki zawierające \(k\) liczb pierwszych dla każdej wartości \(k\).