Informatyczny kącik olimpijski

Liczby prawie pół-pierwsze

Tym razem omówimy zadanie Liczby prawie pół-pierwsze, które pojawiło się na Sobotnim Kole Naukowym (25.11.2017) organizowanym przez Stowarzyszenie Talent w III Liceum Ogólnokształcącym w Gdyni.

Definicja. Liczbę $p$ nazywamy prawie pół-pierwszą, jeśli jest iloczynem dwóch liczb pierwszych $q1,q2,$ gdzie $6 2 ⩽ q1,q2 ⩽ 10 .$ Liczby $|14 = 2⋅7$ i $49 = 7⋅7$ są prawie pół-pierwsze. Natomiast liczby $|30 = 2 ⋅3⋅5$ i $2000000014 = 2 ⋅1000000007$ nie są prawie pół-pierwsze.

Zadanie. Dane są dwie liczby całkowite $|a$ i $b(2 ⩽ a⩽ b ⩽ 1012).$ Oblicz, ile jest liczb prawie pół-pierwszych na przedziale $[a,b].$

Rozwiązanie $|O$
Pierwszy pomysł, który nasuwa się po przeczytaniu treści, polega na przejrzeniu wszystkich liczb całkowitych z przedziału $[a,b]$ i zliczeniu tych, które są prawie pół-pierwsze. Liczba prawie pół-pierwsza zawiera dokładnie dwie liczby pierwsze nie większe niż $106$ w rozkładzie na czynniki pierwsze. Rozkład na czynniki pierwsze liczby całkowitej $|x$ możemy znaleźć w czasie $|O($ (przeglądamy potencjalne dzielniki pierwsze z przedziału $|[2,⌈√ x-⌉]$ ). Rozwiązanie działa w czasie $O((b$

Rozwiązanie $| O$
W tym podejściu, podobnie jak wcześniej, dla każdej liczby całkowitej z przedziału $|[a,b]$ sprawdzimy, czy jest ona prawie pół-pierwsza.

Zacznijmy od stworzenia takiej tablicy $S,$ że $S[i]$ dla każdego $|i∈[2,b]$ oznacza najmniejszy dzielnik pierwszy $|i.$ W tym celu wystarczy nieznacznie zmodyfikować sito Eratostenesa. Zamiast zapamiętywać informację, czy liczba jest pierwsza czy złożona, będziemy pamiętali jej najmniejszy dzielnik, będący liczbą pierwszą. Strukturę budujemy w czasie $|O(b .$ Wówczas w czasie stałym możemy stwierdzić, że:

$p$ jest pierwsze, jeśli: $|S[p] = p,$
$p$ jest prawie pół-pierwsze, jeśli: $-p- -p- -p- 6 S[p] /= p ∧S[ S p ] == S p ∧ S[p],S p ⩽ 10 .$
Wtedy jej dzielnikami pierwszymi są $S[p]$ i $|Sp p-.$

Po wygenerowaniu $S$ zliczamy liczby prawie pół-pierwsze z przedziału $|[a, b].$ Rozwiązanie działa w czasie $O(b .$

Rozwiązanie $|O$
Niech $=106 |M$ oraz $|T[i]$ dla każdego $] |i∈ [2,M$ wskazuje, czy $i$ jest pierwsze $(T [i] = 1),$ czy złożone $|(T[i] = 0).$ Dla pozostałych $i$ niech $|T[i] = 0.$ $|T$ obliczamy za pomocą sita Eratostenesa. Dodatkowo stwórzmy taką tablicę $′ S ,$ że $′ S [i]$ dla każdego $i ∈[a,b]$ będzie oznaczało najmniejszy dzielnik pierwszy $i.$ Konstrukcja $S′$ jest następująca. Najpierw przypisujemy $S ′[i] = i$ dla każdego $|i∈ [a,b].$ Następnie dla każdej liczby pierwszej $|q∈ [2,⌈√ b⌉]$ przeglądamy jej wielokrotności w przedziale $|[a, b],$ czyli liczby $⌈aq ⌉⋅q,(⌈aq⌉ +1) ⋅q,...,⌊bq⌋⋅q,$ i aktualizujemy ich najmniejszy dzielnik pierwszy. Zauważmy, że wielokrotności $|2$ w przedziale $|[a,b]$ jest co najwyżej $b− a- | 2 + 1,$ wielokrotności $|3$ jest co najwyżej $b−a -3- +1$ itd. Zatem konstrukcja struktury zajmuje $|O((b$ operacji.

Na koniec zliczamy liczby prawie pół-pierwsze z przedziału $|[a, b],$ czyli takie $|p∈ [a,b],$ że:

p ′ ′ ∧T[′]=1 S[p] /= p∧ S [p] ⩽M . S[p]

Rozwiązanie $O$
Niech $f N N$ będzie taką funkcją, że $f (x)$ oznacza liczbę liczb prawie pół-pierwszych na przedziale $|[1,x].$ Wówczas liczb prawie pół-pierwszych na przedziale $[a,b]$ jest $f (b)− f(a − 1).$

Opiszemy teraz, jak policzyć $f (x)$ dla $|x ∈[1,1012].$ Zacznijmy od wygenerowania ciągu kolejnych liczb pierwszych nie większych niż $=106.M$ Oznaczmy ten ciąg jako $P = (p ,p ,...,p ). 1 2 k$ Początkowymi wyrazami ciągu są: $p1 = 2,p2 = 3,p3 = 5$ itd. Liczby pierwsze możemy znaleźć za pomocą sita Eratostenesa. Zauważmy, że tylko elementy ciągu $|P$ mogą występować w rozkładzie na czynniki pierwsze liczb prawie pół-pierwszych. Zatem:

f (x) = {(i, j) pip j ⩽x ∧ 1⩽ i⩽ j ⩽k} .

Wartość $| f(x)$ możemy policzyć naiwnie, przeglądając wszystkie pary elementów ciągu $P .$ Niestety takie rozwiązanie jest wolne, ponieważ przegląda się $O(k2)$ par elementów, gdzie $k | = 78498$ (tyle jest liczb pierwszych nie większych niż $106$ ).

Na szczęście możemy to przyspieszyć. Niektóre pary będziemy zliczali "hurtowo". Dokładniej, dla każdego $i∈ [1,k]$ wyznaczymy takie największe $| ji∈ [i,k],$ że $| pip ji⩽ x.$ Jeśli takie $| ji$ nie istnieje, to niech $| ji = i − 1.$ Wówczas liczby postaci $pipi,pipi+1,...,pipj i$ są prawie pół-pierwsze. Zaś wszystkich par jest $|Pi> 1,k ( ji−i + 1).$ Algorytm przebiega następująco. Najpierw naiwnie znajdujemy $j1,$ przeglądając przedział indeksów $| [1,k].$ Następnie kolejno wyznaczamy wartości $| j2, j3,..., jk.$

Obserwacja: Dla każdego $| i ∈[2,k]$ zachodzi $| ji⩽ ji−1.$

Dowód: Wiemy, że $pi > pi− 1$ oraz $∀lA j pi−1pl > x. i 1$ Stąd $|∀lA j pipl > x. i 1$ Zatem $| ji ⩽ ji−1.$

Na mocy powyższej obserwacji, szukanie wartości $ji$ możemy rozpocząć od $| ji−1$ i zmniejszać ją dopóki $| pipj i > x.$ W ten sposób wykonamy $|O(k)$ operacji podczas obliczania $f | (x).$ Całe rozwiązanie działa w czasie $⋅log(log(M))).O(M$