Sito dla rozkładu, ale już nie przeglądem zupełnym

 Stosowałem sito Eratostenesa dla podstawy systemu, dla cyfry dziesiątek. Zostały znalezione przyspieszacze obublikowane w poprzednim poście. 

A teraz przesunąłem obszar rozkładu w pobliże liczby rozkładanej, oraz zajmuję się niezmiennikiem

N = a*p+b

dla którego stosuję własności: 

- b jest dzielnikiem wtedy i tylko wtedy gdy b | a*p, drugim jest np. a+1 w systemie o podstawie p
maksymalny możliwy dzielnik to a (które zresztą maleje w trakcie obliczeń lub wtapia się z p - gdyż mamy dowolność wyboru systemu pozycyjnego).

- w każdej iteracji dla pewnej wartości rosnącej k wyliczam (a-k)*(p+k), co zwiększa b zachowując niezmiennik. Przeskakuję podstawy np bisekcją, dopóki b nie zrówna się z a. Dystans przeskakiwanych wartości jest funkcją słabo malejacą. Podejście to odrzuca liczby pierwsze za duże by być dzielnikami.
Jeśli w podanym kroku uzyskam nierówność b>a, przechodzę na sąsiedni system formułą: 

N = a*p+b = a*(p+1)+(b-a) = a*p'+b'

- jeśli interesują mnie małe liczby pierwsze, stosuję sito dla liczby złożonej a*p-K(), gdzie K() jest ciągłym przerzucaniem wartości podzielnych przez małe liczby  pierwsze na coraz większy iloczyn a*p. Wartości przesuwane są po to, by nie stosować w sicie kroku +1, ale wyznaczony przez kolejną lokalnie największą wartość b. W ten sposób badam równocześnie pierwszość przez małe, jak i przez bardzo duże liczby pierwsze. Krok sita nie jest stały! 

- jeśli w rozkładzie a*p pojawi się większa liczba pierwsza, jest ona ignorowana. Dotychczasowe doświadczenie z przebiegu sit wskazuje, że takie liczby stosunkowo szybko zaczną się przyznawać do swej pierwszości, a jako większe niż b ograniczone maksymalną wartością a, nie będą dzielnikami.  

 

Praktycznie dla liczby nieparzystej możemy nawet zacząć od liczby złożonej 2*a*a+a bliskiej N. Wtedy niejako dołączamy gratis system binarny, co dodatkowo zmniejsza krotność iteracji.Sprawdzanie pierwszości może być z dwu stron - od małych i gigantycznych wartości.

Wyjątkowo nie podaję przykładu i przebiegu - obawiam się to pokazywać osobom spoza branży.