Prime numbers generator explanation?
algorithm, math, primes, python, python-3.x
Solution
Starting with n `True` values in an array, with `i` enumerated from `3` to `sqrt(n)` by the step of `2`, if the `i`th entry in the array is still `True`, set to `False` all entries from `i^2` to the end of the array by the step of `2*i` (these all will be multiples of `i`).
All odd `True` entries above 1 that are left in the array in the end, are prime.
All thus found numbers, and 2, are all the prime numbers that exist below n.
Problem
I was searching for an algorithm to generate prime numbers. I found the following one done by Robert William Hanks. It is very efficient and better than the other algorithms but I can not understand the math behind it. ``` 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]] ``` What is the relation between the array of `True`s values and the final prime numbers array?