Łączę ostatnie pomysły, uzyskując działającą metodę rozkładu. Własności powodują, że przegląd zupełny zachowuje się jak współbieżny (wielowątkowy). Dlatego nie podam dokładnego algorytmu, lecz warunki.
Niech i będzie taką potęgą 2, by
2i <= sqrt n < 4i
Dzielników szukamy przeglądem zupełnym po potęgach dwójki 1<k<i w przedziale [2i, 4i). Każda taka potęga, np. k=2^3 wyznacza warstwę, która jest niezależna od pozostałych.
Co więcej, w tym przedziale występuje dokładnie jedna wartość 3*2^k, gdzie k=i/2, dwie wartości 5*2^k, 7*2^k, gdzie k=i/4 i tak dalej. W metodzie chodzimy po tych niezależnych warstwach, komunikując je wątkiem liczb pierwszych.
Opis ogólny metody
Liczba złożona n jest rozłożona na sumę dwu składników. Jeden ze składników stanowi warstwę związaną z nieujemną potęgą 2, czyli k.
n = k*a*p + c.
Sprawdzamy, kiedy p jest liczbą pierwszą, wtedy pytamy, czy reszta c jest też podzielna przez p, c=d*p. W takim przypadku mamy rozkład:
n = k*a*p + d*p = (k*a+d)*p
Wartość a jest ograniczona bardzo specyficznie, zmniejsza się ze wzrostem p w zakresie swojej warstwy przy stałym k do swojej połowy. Np. dla pewnej wartości przy inicjacji wartości a oraz c są stałe, np:
k * 21 490 565 976 844 * p + 10 378 130 574 991
koniec warstwy następuje, gdy a osiągnie 10 745 282 988 422. Równocześnie p osiąga potęgę 2.
Wartość p jest związana z k w ten sposób, że przy inicjacji jest potęgą 2 oraz p*k=2i, następnie jest zwiększana o 1, przebiega liczby nieparzyste do najbliższej potęgi 2, czyli jest ograniczenie p*k<4i, zaś całość k*a*p oscyluje wokół pierwiastka kwadratowego z n. Oznacza to, że c może przyjmować wartości dowolnego znaku, staramy się, by oscylowało wokół a, gdyż w szczególnym przypadku a=c też możemy natrafić na dzielnik n = k*a*p+a = (k*p+1)*a. Wartości k*p bywają bardzo duże, wprowadzone oscylacje dają nam pewność, że jesteśmy najbliżej potencjalnego dzielnika jak się da przy tym znaku c.
Możemy wykonywać obliczenia niemal równocześnie po warstwach z różnymi k.
W obrębie warstwy myślę stosować sito Eratostenesa oraz kopiec na trzymanie par (liczba, jej dzielnik), posortowany według liczb.
Wątek liczb pierwszych
Wątek ten komunikuje się z dowolną z warstw dla danego k, niszcząc je po wykorzystaniu.
Jego zadaniem jest wstawienie świeżo znalezionej (przysłanej z jakiejś warstwy) nowej liczby pierwszej do kopców w odpowiednich warstwach, podawanie zakresu minimalnej liczby pierwszej oraz zatrzymanie w przypadku znalezienia dzielnika albo wykrycia, że liczba n jest pierwsza.
Jeśli warstwa przyśle nowo wykrytą liczbę pierwszą q, stosujemy następujacą procedurę, szukamy wątku o największym k, w którym któraś z wartości p jest równa q, oraz dodajemy do kopca parę (q,q). Teraz szukamy warstwy zawierajacej iloczyn 3q, wstawiajac parę (3q, q). To nie musi być wątek z połową k, lecz z czwartą częścią k.
Teraz modyfikujemy wielokrotność q tak, by była nie większa niż p w inicjacji. W tym celu powinniśmy czasem dodać q. Dla wątku wielokrotność ta ma być nieparzysta, dodajemy mu parę ((s+1[+1])*q,q), jedna suma opcjonalnie, dla nieparzystości. Staramy się trzymać wielokrotność s*q za małą do umieszczenia w wątku.
Przykład, q=11:
Pierwsza odpowiednia warstwa powstała z p=8, odkładamy jej (11,11), następna warstwa z wartością nieparzystą to (33,11), a to jest warstwa z p=32. Pamiętamy jednak q=22. Mnożymy to przez 2 i dodajemy 11, uzyskując s*q=55, jest to ta sama warstwa z p=32. Dodajemy 11 uzyskując wartość większą niż 64, zatem warstwie z p=64 dodajemy ponownie 11 dodając do kopca parę (55+22, 11). Znów podwajamy s 2*55=110, ale 110+11 = 121 jest mniejsze niż p=128, to jest nasza nowa wartość s. Warstwie dla p=128 dokładamy element (121+22, 11). I tak dalej.
Jeśli warstwa przekaże, że skończyły się jej elementy, wątek liczb pierwszych podwaja zakres najmniejszej możliwej liczby pierwszej i każe warstwom sprawdzić swoje wartości. Wykorzystaną warstwę kasuje.
Jeśli skończą się elementy ostatniej, najdłuższej warstwy, z k=2, liczba jest pierwsza.
Działania na warstwach przy stałym k
Pierwszym działaniem po inicjacji jest przejscie na p nieparzyste. Wystarczy konwersja o 1: k*a'*(2p)+c' = k*a*(2p+1)+c. Uzyskamy p = 1+2^t dla pewnego t. Zapamiętujemy całe ostatnio obrabiane wyrażenie.
Wartość p jest albo liczbą pierwszą, albo złożoną. Sprawdzamy, czy ta wartość jest na szczycie kopca. Należy to powtarzać, gdyz jedna wartość może wystąpić tyle razy, ile ma różnych dzielników. Jeśli jej nie ma, lub jest to para (p,p), mamy duże szanse przypuszczać, że p jest liczbą pierwszą. Zwiększamy ją do najbliższej potęgi 2, z której wyciągamy pierwiastek kwadratowy i porównujemy z zakresem minimalnej liczby pierwszej wątku liczb pierwszych. I tak jeśli zakresem tym jest 8, a my mamy wartość p nieparzystą mniejszą niż 64, mamy do czynienia z liczbą pierwszą. Innym sposobem jest spierwiastkowanie, ale nie znajdujemy liczb pierwszych w porządku liniowym. Ta wartość wtedy czeka, a my możemy spokojnie zająć się kolejną, korzystając z kopii jej współczynników.
Jeśli wartość jest poza zakresem minimalnej liczby pierwszej, musimy poczekać, aż wątek liczb pierwszych go zwiększy. Wtedy moze okazać się, że liczba jest pierwsza, wtedy zwracamy ją wątkowi liczb pierwszych jako liczbę pierwszą.
Zarazem uruchamiamy procedurę sprawdzajacą, czy wartość c jest wielokrotnoscią liczby p. Jeżeli trzymam c w systemie o podstawie p, jest to po prostu porównanie najmniej znaczącej cyfry c z p w warstwie o największym k. W pozostałych warstwach należy sprawdzać podzielność bardziej standardowo.
Ale wąŧek liczb pierwszych może wprowadzić nową wartość większą niż aktualnie obsługiwana. Oznacza to, że oczekująca wartość m jest złożona, znamy jej dzielnik, więc wprowadzamy ją do obróbki jak liczbę złożoną.
Liczbę złożoną m o znanych dzielnikach rozkładamy. Może wtedy pojawić się dodatkowy dzielnik, który jest przesyłany jako nowy wątkowi liczb pierwszych.
Odkładamy na kopiec kolejne liczby podzielne przez q, (m-2q, q).
Mamy liczbę pierwszą p oraz przyrost w, jaki nas dzieli od ostatnio obrabianego wyrażenia p'. Liczba w jest parzystą.
Przystępujemy do konwersji:
k*a'*(p-w)+c' = k*a*p+c
gdzie najczęściej w=2. W później jednak możemy mieć często przyrost będący różnicą między kolejnymi liczbami pierwszymi.
Najpierw należy obliczyć przyrosty Delta a oraz Delta c
k*a*w = k* Delta a * p + Delta c
a następnie odjąć te przyrosty od zapamiętanego wyrażenia. Z Delta a nie ma kłopotu, jest to zwykłe a'*w z wyzerowaną cyfrę najmniej znaczącą.
Jednak Delta c wymaga nieco zachodu. Jeśli a'<c', odejmiemy iloczyn k oraz cyfry najmniej znaczącej a'*w od c'. Jeśli jednak a'>c', skorzystamy z własności systemu niedziesiątkowego, oraz dodamy dodatkowo k*p, zabierając jedynkę z a. W ten sposób zamiast zmniejszać c', zwiększamy je.
Przykłady
Możemy liczyć dziesiętnie, jak w tym przykładzie z p'=17 na p=19:
k*a'*(p-2) + c' =
n = 4 398 046 511 104 * 20 226 415 037 029 * 17 + 58 756 642 197 135
przyrosty:
4 398 046 511 104 * 20 226 415 037 029 * 2 =
4 398 046 511 104 * (2 129 096 319 686 * 19 + 5) =
4 398 046 511 104 * 2 129 096 319 686 * 19 + 105 553 116 266 496 =
k * Delta a * p + Delta c
oraz ich odejmowanie od a', c', gdyż a'<c' (20... < 58...):
20 226 415 037 029 - 2 129 096 319 686 = 18 097 318 717 343
58 756 642 197 135 - 105 553 116 266 496 = - 46 796 474 069 361
nowa postać
n = 4 398 046 511 104 * 18 097 318 717 343 * 19 - 46 796 474 069 361
stąd wyznaczamy, że 19 nie dzieli n, bo 46 796 474 069 361 = 1 (mod 19)
Jednak wolę systemy niedziesiątkowe, gdyż dla większych wartości mamy lepiej widoczne działania (separator 'cyfr' to przecinek, dopuszczam 'ujemne'). Najpierw zapisuję wszystkie współczynniki przy podstawie p (3 dodatkowe proste konwersje:
k * a' * (p-2) + c' =
n = 1022, 2056, 1018 * 311, 3962, 172, 1680 * 4097 + 874, 1430, 3799, 918
przyrosty (wartość 1022, 2056, 1018 to duża potega 2):
1022, 2056, 1018 * (311, 3962, 172, 1680 * 2) =
1022, 2056, 1018 * 622, 7924, 344 * 1,0 + 1022, 2056, 1018 * 3360 =
1022, 2056, 1018 * 622, 7924, 344 * 1,0 + 838, 643, 2179, 1914
nowa postać (znów a'<c'):
n = 1022, 2056, 1018 * 311, 3340, -7752, 1336 * 1, 0 + 36, 787, 1620, -996
oraz sprawdzamy podzielność -996 = 3103 (mod 4099) z 4099. Od razu widać, że liczba n jest niepodzielna przez liczbę pierwszą 4099.
Ale przechodząc na 4101 mamy a'>c', czyli oprócz odejmowania wyznaczonych przyrostów dodamy przekonwertowaną na system 4101 liczbę 1022, 2056, 1018 z systemu o podstawie 4099 pomnożoną przez 4101, by zwiększyć c.
już dla p=4099 działamy na liczbach co najwyżej czterocyfrowych, a dalej mamy jeszcze mniej cyfr, przez co mamy coraz mniej działań. I konwersje są coraz prostsze. Najwięcej przypadków jest dla małych k, najwiecej obliczeń dla dużych.
Inne własności, badajac 65 = 5 * 13 i znając zakres od warstwy k=2^45 (czyli liczbę pierwszą 3 i minimalny zakres 4) wnioskujemy, że 13 < 4^2 też jest pierwsza. Wartość 13 jest jedną z ostatnich sprawdzanych w swojej warstwie (9, 11, 13, 15).
Można przechodzić szybciej, np. z p'=263 na 267, szukając przyrostów iloczynem k*a'*4.
Przebieg.
Inicjacja, mamy w każdej warstwie wyrażenie na n, w którym p jest postaci p=1+2^t dla odpowiedniego t, czyli: 3, 5, 9, 17, 33, 65, 129, 257, 513, 1025,...
kopce puste. Liczymy po jednym elemencie każdej warstwy.
Sprawdzamy liczbę pierwszą 3, do kopca każdej warstwy odkładamy najmniejszą parę liczby podzielnej przez 3 większą niż potęga 2^t. Kasujemy pierwszą warstwę.
Wartości 9, 33, 129, 513 są w kopcu. Liczby mniejsze niż 4^2 nie będące w kopcach są pierwsze. Wartość złożona 15 jeszcze nie jest w kopcu, ale pojawi się tam podczas obsługi wątku p=9.
Wartość 5 nie jest w kopcu, jest pierwsza, kopce powiększają się o tę wartość.
Wartość 9, byłaby zignorowana, ale mamy wyrażenie dla niej z inicjacji. Dalej w takim przypadku tylko zwiększamy przyrost w o 2. Ale do kopca odkładamy wartość (9+6,3) czyli (15,3). Teraz wszystkie liczby złożone nieparzyste mniejsze niz 16 są w kopcach.
Wartości 17, 257 czekają, na tym etapie nie wiemy, czy są pierwsze. Sprawdzamy, czy ich potrojenie mieści się w ograniczeniu warstwy i ewentualnie odkładamy do kopca.
Wartości 33=3*11, 65=5*13 wyznaczają nowe liczby pierwsze. Wartość 513 = 3^3*57 czeka na możliwość stwierdzenia, czy 57 jest pierwsza (wymaga skasowania warstwy z p=4). Sprawdzana podzielność c przez 11, 13.
Podobnie 1025.
Nowy przebieg po warstwach.
Wartość 5+2=7 nie jest w kopcu, jest pierwsza. Warstwa kasowana, zakres minimalnej liczby pierwszej zwiększa się do 8^2=64.
Wartość 9+2=11 pierwsza, bo w kopcu jest (11,11). Podzielność jest sprawdzana w wartwie 33, tu można zignorować.
Wartość 17+2 = 19. Wynik z warstwy 7 wskazuje, że 17 jest pierwsza. Ale rozpatrywana 19 też jest pierwsza. Odkładamy ich nieparzyste wielokrotnosci do kopców w obrębie ograniczeń warstwy, czyli w tej warstwie już nic.
Wartość 35 = 5*7 ignorujemy tylko wstawiając do kopca pary (45,5), (49,7), Są w tej warstwie. Mamy w kopcu dwie pary (45,3) oraz (45,5). Może zrobić listę (45, [3,5])?
Wartość 67 jest pierwsza. Wiadomo, co... Dla kolejnych dwu wartości 131, 259 podobnie.
Wartość 515. Teraz już wiemy, co z 57 z 513 (pierwsza). Testujemy podzielność. W przypadku liczby złożonej czekamy na dalsze informacje. Obrabiamy 515.
... I tak dalej...
