Wspominałem już o możliwościach przeglądu zupełnego za pomocą sita. Wtenczas potrzebowałem jako lemat tablicę liczb pierwszych nie większych niż pierwiastek czwartego stopnia z liczby rozkładanej.
W tej wersji nadal pozostanie struktura stogu, w której odkładam parę:
[podstawa systemu p, lista jej znanych dzielników pierwszych d_i]
struktura działa tak samo ja opisałem wcześniej: po pobraniu wartości, zanim ulegnie skasowaniu, odkłada na stóg wartości [p - d_i, d_i] dla wszystkich znanych dzielników p.
Wówczas należało odróżnić dzielniki wykryte od już przetestowanych. Teraz w strukturze tej odkładane są tylko znane liczby pierwsze, sprawdzone pod kątem podzielności.
Potrzebuję drugiej struktury: listy par, w której trzymam duże wartości będące iloczynami liczb pierwszych lub takimi liczbami, oraz albo ich wartość początkową, albo odległość (dystans) od miejsca startowego algorytmu. Jest to niezbędne, gdy przy wyznaczaniu odległości znajdujemy liczbę pierwszą, aby ją właściwie umieścić w strukturze stogu. Wygodniej jest użyć odległości, chociażby z uwagi na mniejszą wartość choć bardziej skomplikowane jest wtedy znalezienie wielokrotności aktualnego dystansu.
Jak to wygląda w praktyce - na początku.
Liczbę rozkładaną n przedstawiam w postaci
n = (a*p+b)*p+c
np. n = (1 * 38 8878 4050 9055 + 2)* 38 8878 4050 9055 - 21 1614 4142 3728
Wartością początkową będzie bliska pierwiastkowi kwadratowemu b= 38 8878 4050 955, którą w każdej iteracji zmniejszamy o 1 do połowy jej wartosci, lub przez odpowiednio dużą potęge 2^i ( 2^i < sqrt n < 2*2*i ). Równie dobrze możemy przesunąć do najbliższej potęgi 2 większej niż pierwiastek kwadratowy z n, przyjąć a=1 oraz b ujemne.
Liczbę możemy równoważnie zapisywać na inne sposoby:
n = (1 * 38 8878 4050 9055 + 1)* 38 8878 4050 9055 + 17 7263 9908 5327
n = (1 * 38 8878 4050 9060 - 9)* 38 8878 4050 9060 + 17 7263 9908 5347
n = (1 * 70 3687 4417 7655 - 48 8781 7820 0808) * 70 3687 4417 7655 - 7 3130 0816 6378
Dobór, według wielkości wartości, wartości początkowych itp.
W poprzednim algorytmie znajdowałem, że
38 8878 4050 9055 ma dzielniki: 5, 19, 41, 239, 177 4231, i dzieliłem c = 17 7263 9908 5327 przez każdy z nich.
Teraz nie znam tych dzielników, zatem w strukturze listy par odkładam np. wartość 38 8878 4050 9055 i tą samą wartość (odległość 0). Po czym obliczam największy wspólny dzielnik
gcd( 38 8878 4050 9055 , 17 7263 9908 5327 )
zatrzymując, gdy wartość gcd() zmniejszy się poniżej odległości. W strukturze stogu nic na razie nie odkładam. W ten sposób wiem, że dzielniki tej liczby są względnie pierwsze z liczbą rozkładaną, nie znając jeszcze tych dzielników. No chyba że znajdę dzielnik całej liczby, zwrócony przez gcd()!
Biorę następną wartość z podstawą mniejszą o 1, ze zwiększoną odległością o 1, w której modyfikuję konwersją: b=b+2, c = c+b-a, wartość n jest niezmiennikiem:
n = (1 * 38 8878 4050 9054 + 4)* 38 8878 4050 9054 - 21 1614 4142 3725
Wśród obu wartości p, p-1 dokładnie jedna jest parzysta, zatem w strukturze par dzielę przez odpowiednie potęgi 2 zmniejszając wartość pierwszego elementu pary, i znajduję pierwszą liczbę pierwszą, która zaznacza pozycje parzyste w strukturze stogu:
[38 8878 4050 9054-2 ; 2]
W drugiej strukturze wyeliminowane są zarazem wszystkie wystąpienia 2. Jest ona tylko w stogu, i ta liczba pierwsza zmniejsza podstawę p dla liczenia wspólnego dzielnika.
Przyjmując następną wartość, wiem, że spośród wszystkich odłożonych w strukturze par i pobranej, co najwyżej jedna jest podzielna przez aktualną odległość. Jeśli jej nie znajdę, odległość jest liczbą złożoną, z już uwzględnionymi czynnikami pierwszymi.
Myślałem, by sprawdzać kolejno wszystkie wartości struktury par w poszukiwaniu właciwej, a po jej znalezieniu, podzieleniu przezeń. Ale widzę szybszy sposób, mam dwa wskaźniki, jeden na wartość największą struktury, drugi na najmniejszą, zaś wartości z jedynką usuwamy ze struktury. Jest to potrzebne z dwu powodów: wartość największa wskazuje resztę z dzielenia wskazywanej podstawy przez aktualny dystans, co w prosty sposób wskazuje właściwą wartość, którą normalnie dzielimy. Jest podzielna, uzyskujemy nową liczbę pierwszą do wyeliminowania ze struktury par i przeniesienia do stofu (zarazem już sprawdzona, że nie jest dzielnikiem n).
Jeśli po wyrugowaniu znalezionej liczby pierwszej ze struktury par uzyskamy wartość 1, kasujemy parę. Sprawdzamy, która jest najmniejsza, jeśli okaże się, że najmniejsza jest tylko dwucyfrowa w systemie o podstawie dystansu, jest to kolejna liczba pierwsza do wyrugowania, tzn. przeniesienia do stogu.
Np.
struktura par ma wartości (punkt startowy 70 3687 4417 7664 - potęga 2)
dystans 2 wartość 35 1843 7208 8831
dystans 3 wartość 70 3687 4417 7661 (największa)
Po kilku iteracjach znajdziemy się w odległości 7 od punktu startowego, czyli podstawą jest 70 3687 4417 7657. Sprawdzamy liczbę 7, szukając reszty z dzielenia przez 7 wartości z dystansu 3. Znajdujemy resztę 6, czyli przez 7 podzielna jest liczba z dystansu 3-(7-6)=2.
Mamy nową wartość dla tego dystansu po wyrugowaniu liczby pierwszej 7
dystans 2 wartość 5 0263 3886 9833
I wiemy, że liczba nie dzieli się przez 7, co sprawdziliśmy kilka iteracji wcześniej. Po kolejnych dwu iteracjach dystans wrazsta do 9. Reszta sugeruje, ze liczba ta znajduje się dla dystansu 7, ale mamy tam wartość 7 8187 4935 3073, która nie jest podzielna przez 9, zatem dystans 9 = 3*3 jest liczbą zlożoną z uwzględnionymi już czynnikami. Ta ogromna wartość jest liczbą pierwszą, która rozpoznana jako pierwsza przejdzie do stogu dopiero przy dystansie 2796203.
I ten sposób sprawdza początkowo dosyć szybko małe liczby pierwsze i giganty. Z biegiem czasu mniejsze liczby pierwsze rozkładają podstawę systemu stogu, tak że wspólny dzielnik od razu jest widoczny, A po jeszcze dłuższym okresie zostają do sprawdzenia tylko liczby pierwsze, często większe niż podstawa systemu.
Są one wyłapywane przez ich nieobecność w strukturze stogu podczas pobierania kolejnej wartości o 1 mniejszej, lub przechodzą ze struktury par przy dużym dystansie.
Brak komentarzy:
Prześlij komentarz