Jak mogę wykorzystać Sito Eratostenesa, aby uzyskać nth prim?

Question

Napisałem funkcję, sieve(n), która używa Sieve of Eratostenes, aby zwrócić tablicę wszystkich liczb pierwszych do n.

sieve(25) # ==> [2, 3, 5, 7, 11, 13, 17, 19, 23] 

Źródło tej funkcji można odczytać here.

Chcę to zmienić teraz, aby sieve(n) zwrócił n th prime. Po prostu nie jestem pewien, jak to zrobię. Nie chcę napisać zupełnie nowej, bardziej rozbudowanej funkcji, więc wydaje się, że najlepszą metodą jest ustalenie, do jakiej wartości powinno się liczyć sito.

Na przykład, jeśli mogę prosić o sile 27, sita za Wstępna lista liczb powinna wynosić 2 do (coś wiem 27. prime nie jest większa niż). Ale czy istnieje prosty sposób sprawdzenia, jaka jest ta wartość?

że badane na to pytanie, a znaleziono this Quora post którym wymienione, że n-ta pierwsza musi być pomiędzy n*Math.log(n) + n*(Math.log(Math.log(n))-1) i n*Math.log(n) + n*Math.log(Math.log(n)) (gdzie Math.log Ruby dla logarytmu naturalnego), ale po prostu dzięki czemu list tablica numerów między tymi dwoma postaciami sprawia wydajność sita dziwne wartości, takie jak 56 dla 15th prim (56 nie jest liczbą pierwszą, a odpowiedź powinna być 47).

Jak można się domyślić, jestem całkowicie poza moim żywiołem. Gdyby ktoś mógł mi doradzić, naprawdę bym to docenił.

Answer 1

Sito Eratostenesa zawsze musi zaczynać się od początku; nie możesz przesiać w dowolnym odstępie czasu, ponieważ stracisz wszystkie mniejsze liczby pierwsze. Więc nie musisz dbać o dolną granicę, tylko dla górnej granicy. Który dałeś, i które Wikipedia potwierdza:

p _n < n ln ( n ln n) dla n ≥ 6

Więc po prostu wziąć to związane, korek w twoim n i iteruj dopóki nie znajdziesz liczb pierwszych. Twoje sito będzie zwykle nieco za duże, ale nie za dużo, jeśli granica jest rozsądnie ciasna, czego się spodziewam.

Patrz tabela here dla tabeli tego ograniczenia lub here dla wykresu. Nawiasem mówiąc, kod tworzący tabelę robi to samo. Chciałem przynajmniej 500 wpisów, więc obliczane

n = 500 
lst = list(range(2, ceil(n*log(n*log(n))))) 
ps = [] 
while lst: 
    p = lst[0] # next prime 
    ps.append(p) 
    lst = [i for i in lst if i % p != 0] 

i dostał trochę ponad 500 liczb pierwszych z niego, za które następnie mogłyby pokazać jak Wyliczony związany porównuje się do wartości rzeczywistej.