Wyjaśnienie generatora liczb pierwszych?

Question

Szukałem algorytmu do generowania liczb pierwszych. Znalazłem następujący wykonał Robert William Hanks. Jest bardzo wydajny i lepszy niż inne algorytmy, ale nie mogę zrozumieć matematyki za nim.

def primes(n): 
    """ Returns a list of primes < n """ 
    lis = [True] * n 
    for i in range(3,int(n**0.5)+1,2): 
     if lis[i]: 
      lis[i*i::2*i]=[False]*int((n-i*i-1)/(2*i)+1) 
    return [2] + [i for i in range(3,n,2) if lis[i]] 

Jaka jest relacja między tablicy True s wartościami oraz ostatecznej liczby pierwsze tablicy?

Answer 1

Począwszy nTrue wartości z i numerowane od do sqrt(n) w etapie jeśli i pozycja p nadal True, znak wszystkie wpisy z i^2 do końca tablicy kroku z 2*i jako False (będą to wielokrotności i).

Wszystkie nieparzyste wpisy True, które pozostały w tablicy na końcu, są liczbami pierwszych.