Sto Eratostenesa, pamięć tylko dla jednej wielokrotności liczb pierwszych

Sito Eratostenesa w najczęściej podawanej formie zaczyna się:
weźmy tablicę wszystkich liczb naturalnych począwszy od 2...
a potem skreślane są kolejne wielokrotności znalezionych liczb pierwszych.

A przecież liczb pierwszych jest mniej, dlatego proponuję modyfikację obliczeniową tego sita.
Mamy strukturę [liczba, {dzielnik_iczby} ]. Liczby złożone mają wskazane w zbiorze dzielnik_liczby namiary na liczby pierwsze dzielące daną wartość.
Przechodzimy po liczbach naturalnych jednorazowo (w oryginalnym sicie przy każdej napotknej liczbie pierwszej).
Jeśli dla wartości n taka struktura jeszcze nie występuje, jest liczbą pierwszą. Tworzymy z niej strukturę
  [n+n,{n}],
która wskazuje kolejną wielokrotność n. 
Dla każdej napotkanej liczby złożonej o dzielniku k tworzymy struktury
  [n+k, {k}] 
dla wszystkich możliwych dzielników k.
Użytą podczas przechodzenia strukturę można już skasować. 

W ten sposób podczas przechodzenia po kolejnych liczbach naturalnych mamy zaznaczone wartości złożone istnieniem struktury dla nich, tracimy pamięć tylko na aktualną liczbę oraz najbliższe liczby złożone dla znanych liczb pierwszych. Nie musimy pamiętać pozostałych.

Dodatkowo struktury mogą tworzyć kopiec sortowany po wartości liczba, by mozna było szybciej sprawdzić, czy struktura dla danej wartości istnieje.


Przykład, już dotarliśmy do liczby 10, mającej dwie struktury  z dwu dzielników:
[10, {2,5}]]
w strukturach mamy:
[12, {3}]
[14, {7}]
Tworzymy dwie nowe struktury, dla 2 i 5, jedna doczepia się do utworzonej już 12, druga generuje nową wartość:
[12, {2,3}]
[15, {5}]
i możemy skasować strukturę dla liczby złożonej 10.
Następna wartość to 11, struktura nie istnieje, jest to liczba pierwsza. Tworzymy dla niej strukturę
[22, {11}]
Zaś następna wartość 12 jest znów złożona, jak 10.
I pamiętamy raptem na tym etapie 4 struktury (jedna ma dwa dzielniki) dla liczb pierwszych 2, 3, 5, 7, 11 i wartość aktualną 12...


Podejście można odwrócić,  by szukać jak największej liczby pierwszej mniejszej niż zadana. W tym przypadku można narzucić dodatkowe ograniczenie na powstawanie struktury - dzielnik nie jest większy niż pierwiastek kwadratowy danej liczby, zaś formułą jest [n-k, {k}].

Modyfikacja zmiennej pętli for

Wyczytałem chyba na wazniak.mimuw.edu.pl, że zmiana zmiennej sterującej pętli for świadczy o nieumiejętności programowania.
I tak pętla:
for( int k=0; k<liczba; k++ ) {
   ...
   k++; 
}
może być traktowana jak napisana przez bardzo niedoświadczonego, gdyż można użyć
for( int k=0; k<liczba; k=k+2 ) {
   ...
}

A teraz podam przykład, w którym jednak taka konstrukcja się przydaje.
Mam tablicę do 8 różnych obiektów. Należy ją zainicjować. Obiekty są różne, nie mogą się powtarzać. Ich krotność jest losowa od 1 do 8.
Np. sud szpitalny. Pacjent ma do 8 różnych chorób, które należy zainicjować. Każda choroba ma moc będącą liczbą losową od 1 do 100.
Losujemy chorobę, wstawiamy ją do tablicy, o ile się nie powtarza. Kiedy się powtórzy, powtarzamy losowanie. Ale niedoświadczony lekarz zna zaledwie dwie choroby. Czyli i tak musimy siłowo zmniejszyć krotność chorób z 8 do co najwyżej 2!
Zastosowane rozwiązanie: illnes = tablica chorób, jest ich ILLNESES, pacjent ma wylosowane możliwych k różnych chorób
1. for( int i=0; i<k; i++ ) {
2.   illnes[i] = 1+rand()% (ILLNESES-1); // losowana choroba z puli
3.   for( int j=0; j<i; j++ )
4.      if( illnes[j] == illnes[i] ) {  // choroba juz wystapila
5.         i--;
6.         k--;
7,      }
8.   ... // ustawienie parametrow chorob
9. }
10. for( int i=k; i<8; i++) illnes[i]=-1;  // nie ma dalszych chorob

Warunek w linii 4 sprawdza, czy choroba została już wylosowana, gdy tak, ignoruje ten wybór pozwalając nadpisać powtarzajacą się chorobę, zmniejszając zarazem ich krotność. Nadpisanie to następuje albo w linii 8, albo w 10.

Nie wyobrażam sobie, jak bardzo skomplikowany byłby kod sprawdzania możliwych dostępnych chorób bez tej modyfikacji...

Stała w złożoności przeglądu zupełnego

Przegląd zupełny do wartości pierwiastka sześciennego z rozkładanej liczby odbywa się po wszystkich nieparzystych wartościach. Nawet dalej, ale niekoniecznie do pierwiastka kwadratowego.
Można przyspieszyć przegląd przy małych a, gdyż
niech n = (a*p+b)*p+c.
dla ustalonego a wartość b tworzy funkcję monotoniczną od zmian podstawy p.

Jeśli dla podstawy parzystej mamy sumę a+b bliską p przy ustalonym a (a tak jest blisko dzielnika), zmienia się głównie b, c jest szumem. Zatem wystarczy tylko sprawdzać wartości z różnym a. Tych zaś jest też nie więcej niż pierwiastek sześcienny. Dodatkowo dla postaw bliskich pierwiastkowi sześciennemu a zmienia się o 2, nie o 1. Oszacowanie jest zawyżone.

Zatem stałą złożoności przeglądu zupełnego można związać nie tyle z pierwiastkiem kwadratowym, co sześciennym rozkładanej liczby.
Szczegóły tej ostatniej fazy z małymi a nie są jednak jednoznacznie wyznaczone. Warunek a+b=p nie wskazuje dokłądnie dzielnika, lecz wartość przybliżoną. Należy zastosować drugie kryterium, które działa dla przesuniętej wartości p o 2: naprzemienna suma jest równa zero, ale nie mamy jednak tutaj zbieżności, lecz skok. Zbieżność możemy uzyskać, gdy zapiszemy b oraz c w bardzo specyficznej postaci, zmieniając p z odpowiedniej strony:
a*p^2 + (a+b)*p + (b-c) = n
c dąży do b, a jest ustalone. 


    Jeszcze jeden przebieg konwersji dla gigantycznych a, małych p.
Można spakować wszystkie cyfry większe niż cyfra setek do cyfry setek bez utraty danych. Konwersję o r=2 jest wtedy wygodnie przedstawić: 
ap^2 + bp + c,
gdzie a jest gigantyczne, pozostałe zwykłe cyfry systemu o podstawie p. Przekształcenie rekursywne, najpierw tylko dla a:
a'= a-floor( 2a/(p+2) ), b'=b-remainder(2a/(p+2))
i naprawa, potem powtórzyć jeszcze raz dla wszystkich cyfr.
Wartość z pozycji setek jest szybko tłumiona przy wzroście p.