Я искал алгоритм для генерации простых чисел. Я нашел следующее, сделанное Робертом Уильямом Хэнксом. Это очень эффективно и лучше, чем другие алгоритмы, но я не могу понять математику за ней.
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 и окончательным массивом простых чисел?
Начиная с n значений True в массиве, с i перечисленным от 3 до sqrt(n) с шагом 2, если i-я запись в массиве все еще True, установите все записи с i^2 до конца массива с шагом 2*i в False (это будет кратно i).
Все нечетные записи True, которые остаются в массиве в конце, являются простыми.
Все найденные таким образом числа, и 2, являются всеми простыми числами, которые существуют ниже n.