Wydaje mi się, że działa OK, problemem jest szybkość jego działania.
Tak, działa OK, choć jest wolny z racji zastosowanego algorytmu. Wystarczy wejść na Wikipedię, przeczytać o algorytmie Eratostenesa i go zaimplementować. Przepisałem sobie Twój kod na Pythona i porównałem z moim własnym (wkleję je, bo mogą posłużyć jako pseudokody). Twój kod:
def sieve(down,up):
sup = sqrt(up)
tab = range(down,up+1)
idx = 2
while idx <= sup:
for i in tab:
if i == 1:
tab[tab.index(i)] = 0
if not i % idx and i != idx:
tab[tab.index(i)] = 0
idx += 1
sieve(2,1000000)
Mój kod:
koniec = 1000000
pierwsze = range(koniec + 1)
n = 1
while n < sqrt(koniec):
n += 1
m = n * 2
while m <= koniec:
pierwsze[m] = 0
m += n
Dla N = 1000000 mój kod wykonał się w 2 sekundy, a na Twój mi się nie chciało czekać więcej niż minutę, więc przerwałem program. Zasoby są pożerane przez instrukcje warunkowe. U Ciebie za każdym razem sprawdzane są warunki, u mnie nie ma to miejsca. Po prostu wykreślam wielokrotności kolejnych liczb pierwszych, maskując je zerami. Ty robisz to samo, ale sprawdzasz warunki. A bierze się to stąd, że wprowadziłeś sobie zakres dolny i górny i ograniczasz się tylko do tego zbioru liczb pierwszych. Prościej byłoby iterować od 2 do N, na sam koniec ucinając początek listy.