素数生成器の説明？

Question

私は素数を生成するアルゴリズムを探していました。私はロバート・ウィリアム・ハンクスによって次のものが見つかった。それは他のアルゴリズムよりも効率的で優れていますが、その背後にある数学を理解することはできません。

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]] 

Trueの値の配列と、最終的な素数アレイとの間の関係は何ですか？

Answer 1

ステップによってアレイの端部にi^2からすべてのエントリをマークし、NTrue値、I番目のエントリがまだTrueある場合iと、のステップによってsqrt(n)にから列挙から開始2*iはFalse（これらはiの倍数になります）。

すべての奇数True最後に配列に残っているエントリは、素数です。