Dzień dobry,
ostatnimi czasy zauważyłem, że jest coś takiego jak "Segmented sieve of erastothenes" [czy jakoś tak]
Nie mogę znaleźć żadnych porządnych informacji na ten temat po polsku, a jedynie kilka kodów w internecie, których i tak nie jestem w stanie zrozumieć.
Mamy np. zadanie - znaleźć liczby pierwszy w przedziale od a do b, gdzie b-a <500
oraz 1 <= a < b <= 2^20
Normalnie w sicie Erastotenesa bym zrobił tablicę o rozmiarze b i bym wykreślał po kolei indeksy.
Jednakże jest to kompletnie nieoptymalne, gdyż tych liczb jest mniej niż 500, a ja rezerwuję aż 2^20.
Ale to nawet nie chodzi mi o to, że nie jest optymalne, tylko o to, że nie jestem w stanie takiej tablicy utworzyć (przekroczona pamięć programu?)
I tutaj właśnie przychodzi te posegmentowane sito, którego działania nie rozumiem.

Pytanie moje brzmi: Czy mógłby mi ktoś wytłumaczyć - jak zamiast tworzenia tablicy o rozmiarze 2^20 można by to zrobić? A raczej jak działa ten algorytm?

Ale już 2^30 nie...
Chodzi mi o ogólną zasadę, a to tylko przykład.

Dyzio zrobiłem, ale normalnym sitem...
dla większej ilości liczb (w sensie górny zakres) już nie dałoby tak rady.

Dzięki, przyjrzę się bliżej temu, co podesłałeś