Aby sprawdzić, czy liczba jest pierwsza wprost, wystarczy 7+4(n-sqrt n) operacji porównywania, dodawania lub odejmowania.
Inicjowanie: a=(n-1)/2, po czym b=a-1, a++, r=2. Łącznie 7 operacji (z przypisaniami włącznie).
Uzyskamy a=(n-1)/2+1; b=(n-1)/2-1; r=2, które jest specjalnym rozwiązaniem pewnej tożsamości, o niej dalej.
Teraz pętla, w której wykonujemy przekształcenia:
r-=a; a--;
albo
r+=b; b--;
oraz warunki wyjścia z pętli:
if( 0==r ) dla liczb złożonych
if( 0==b ) dla liczby n pierwszej
Pętla wykonuje się n-sqrt n razy, gdyż albo zwiększamy r, albo je zmniejszamy.
Dlaczego akurat tyle, i dlaczego to działa?
Każdą liczbę naturalną można przedstawić jako różnicę sum
1+2+...+k = k(k+1)/2 = H(k),
chociażby w trywialny sposób H(n+1)-H(n). Ale są też inne możliwości, związane z dzielnikami.
Weżmy taką tożsamość dla podwojonej liczby n, by zlikwidować dzielenie we wzorach na H(k), jest to zarazem niezmiennik pętli równy r.
2n = H(a)-H(b) = a(a+1) - b(b+1) = (a-b)(a+b+1) .
Zauważmy, że ostatnie dwa czynniki różnią się parzystością. Podwojenie było niezbędne.
Niech n będzie parzyste, wtedy 2n = 1*(n+(n-1)+1). Wystarczy wziąć a=n, b=n-1.
Niech n będzie nieparzyste, wtedy 2n = 2*(((n-1)/2 +1)+ ((n-1)/2 - 1) + 1).
To są właśnie startowe wartości dla inicjacji.
Zmniejszamy długości H(k) zabierając ostatni składnik sumy, starając się trzymać blisko wartości n.
W sposobie faktoryzacji r jest różnicą między n oraz różnicą (H(a)-H(b)). Jeśli r będzie zerem, trafimy na tożsamość, z której dzielniki wyznaczymy jako nieparzyste trywialne dzielniki liczb (a-b) oraz (a-b+1).
Dla liczb pierwszych oraz b nieujemnych startujemy od najmniejszej takiej tożsamości. Zatem żadnej innej już nie znajdziemy. Dla liczb zlożonych występują mniejsze, po dwa dla iloczynu.
Działa ładnie, lecz wolno. Do tej pory jest to algorytm złożoności arytmetycznej liniowej O(n), złożoności stosowanej dla dużych liczb O(N log n).
Warto to usprawnić. Patrząc na przebieg, z początku co trochę dodajemy b, a zaraz odejmujemy a. Można połączyć tworząc nowe przekształcenie
a--; b--; r-=(a-b);
Różnica a-b jest stała! Pozwala to jeszcze bardziej uprościć, opuszczając r/(a-b) przekształceń. Tu wkracza dzielenie.
Już na samym początku widać, że po zwiększeniu r do około n/2, mamy trzecią część z n/2 do opuszczenia, czyli 2n/6 przypadków, by r znów sprowadzić w pobliże zera.
Później róznica wzrasta do 4, oraz po zwiększeniu r o b opuszczamy czwartą część pozostałych przypadków. To są ogromne liczby, dla których nie musimy nic robić.
Ciekawym , jak będzie działał program faktoryzujący tym sposobem.
Oto kilka przykładowych tożsamości stosowanych w sposobie faktoryzacji:
n=127: a=64, b=62, r=0, bo 64*65-62*63 = 2*127
n=51:
a=26, b=24, bo 26*27 - 24*25 = 2*51
a=18, b=15, bo 18*19 - 15*16 = 2*51, 18-15=3, 18+15+1=2*17
a=11, b=5, bo 11*12 - 5*6 = 2*51, 11-5=2*3, 11+5+1 = 17
Znając dzielniki, łatwo wyznaczymy te tożsamości.
A oto i kod w Pythonie (spr. online, tutorialspoints.com):
n = ...# nieparzysta dodatnia
a= 1+(n-1)/2
b= a-2
d=2
r=0
e=2
#print "wstepnie a=",a, " b=",b, " r=",r
while (1<e):
r+=b
d=d+1
k = r/d
r = r%d
a=a-k
b=b-k-1
if (0==r):
e=0
if (1>b):
e=1
#print "a=",a, " b=",b, " r=",r
if( 0==e ) :
print "Dzielniki",n,": "
if( 0==(a-b)%2 ) : print (a-b)/2, a+b+1
else : print a-b, (a+b+1)/2
else : print "Pierwsza"
Brak komentarzy:
Prześlij komentarz