W wielu algorytmach poświęconych situ Eratostenesa zakłada się tablicę zawierającą kolejbe liczby naturalne, do rozkładanej włącznie. Uważam do za duży narzut. Za duży.
Przy podejściu zaczynającym od liczby rozkładanej do coraz mniejszych zakończymy działanie sita przy liczbie pierwszej będącej dzielnikiem, a mniejsze są tylko kolejne wielokrotności liczb pierwszych mniejszych niż dzielnik. Podstawową wadą jest nieznajomość tych liczb pierwszych. Można je sprawdzać na co najmniej dwa sposoby:
- mając już rozkład cząstkowy jakiejś liczby mniejszej niż n, obliczamy jej resztę z dzielenia przez kolejną wartość, co sprowadza się do algorytmu, w którym wyrażenie algebraiczne generuje reszty przez kolejne liczby. Asymptotycznie operujemy na wartościach z zakresu [d, d^2), gdzie d jest stale rosnącą wartością, zaś obliczenia są wykonywane modulo d. No, może jeszcze wystąpić stała mniejsza niż d, która doczepiona do któregokolwiek z czynników zwiększa ją powyżej d^2.
- przy kolejnej wartości d sprawdzamy, czy jest pierwsza, a wtedy liczymy resztę d%p jak przy dzieleniu przez kolejne wartości p jak w standardowym trial division.
W obu przypadkach znalezione wartości pierwsze d propagują się do coraz mniejszych wartości: n-r, n-r-d, n-r-2*d, itd. dla n = k*d+r, 0<=r<d. Warto też dołączać potęgi liczb pierwszych, a do każdej kolejnej wartości n-d stosujemy trial division przez zapamiętane i przypisane liczby pierwsze. Tych dzieleń jest skonczona krotność, i często wiemy z góry, że wielokrotność jest daną potęgą liczby pierwszej, np. sześcianem. Nie trzeba wtedy dzielić przezeń dalej, kiedy w sicie napotkana została jej potęga czwarta lub większa. I od pewnego momentu kolejne większe liczby pierwsze same zaczynają się ujawniać i przedstawiać.
I teraz modyfikacje, choć dalej z tą luką dotyczącą nieznajomości małych liczb pierwszych. Jeśli ich odległość pierwszego wystąpienia jest mniejsza niż d, możemy je zignorować, na pewno nie są dzielnikami. Ale nie daje to pewności, że przy kolejnym ich wystąpieniu je rozpoznamy. Koniecznie należy je wyłapać zanim wystąpią drugi raz przy rozkładzie, albo skakać na ogromne odległości przy ich rozpoznawaniu, co grozi pominięciem dzielnika blisko n -- kryterium podzielności staje się: dystans jest wielokrotnością liczby pierwszej.
Zamiast zapamiętywania kolejnych wartości, zapamiętujemy odległość (dystans d) od liczby rozkładanej. A to można przekształcić w listę par (p,d[]), gdzie p jest liczbą pierwszą, a na liście rosnącej d zamieszczane są odległości występowania kolejnych potęg k>0 od liczby. I tak liczba n-d z pozycji d[2] zawiera jako dzielnik kwadrat liczby p (liczenie od 1). Jeśli nie istnieje d[3], należy sprawdzać możliwość wystąpienia trzeciego dzielnika p, ale jeśli istnieje, to wystarczy jedno mnożenie/dzielenie przez p^2 podczas trial division tej wartości.
Przebieg sita od n:
- początek: wyłączamy potęgę 2 uzyskując nieparzyste n, na stóg para (2, [n-3]), d=2
- pętla, zwiększamy d++;
- szukamy w stogu liczb pierwszych p par (p,d[1]) o tym dystansie (p,d), jeśli nie znajdziemy, bardzo mozliwe, że n-d jest pierwsza, na pewno ma dzielnik większy niż d; jeśli istnieje, przesuwamy się po liście do największego dzielnika będącego potęgą p;
jeśli istnieje liczba pierwsza równa d, to d jest dzielnikiem n;
- wykonujemy mnożenia albo dzielenia rozpoznanych dzielników w poszukiwaniu kolejnych wartości, które są albo równe n-d (mnożenie, przy dzieleniu 1), albo liczbami złożonymi o dzielnikach większych niż d, albo liczbami pierwszymi; ostatni przypadek jest dla wartości a zakresu 1<a<d^2 przy dzieleniu;
- odkładamy na stóg pary (p, [d+p, d+p^2, ..., d+p^k]), gdzie p^k są potęgami liczby pierwszej p, dla wszystkich dzielników n-d; sortowanie po dystansie d[1] =d+p;
- usunięcie luki związanej z nieznajomością liczb pierwszych: sprawdzenie, czy d jest pierwsza, jeśli tak, odkładamy nową parę (d,d+r) na stóg, gdzie r wyznacza się np. jako (d-(n%d))+d, chodzi o to, by d|(n-d-r); w tym kroku też możemy uzyskać, że d jest dzielnikiem n;
- kryterium stopu d*d>n, lub powrót na początek pętli.
Takie tablice mają interpretacje np. dystans d=259, liczba pierwsza 7:
(7, [264, 264, 411, 2469])
7 | (n-264), 7^2 | (n-264), 7^3 | (n-411), zaś n-2469 ma jako dzielnik 7^4 z możliwością wysŧąpienia kolejnych potęg 7.
Pamiętamy tylko liczby pierwsze, co znacząco zmniejsza zapotrzebowanie na pamięć, o ile poradzimy sobie ze wspomnianą luką. Sprawdzone wartości n-d można spokojnie zapominać, modyfikując kolejne odległości.
Dodatkowo, odległości są znacznie mniejsze niż wartości n-d, co ma kolejne znaczenie dla większych wartości.
Brak komentarzy:
Prześlij komentarz