了解快速素数生成器

Question

def sieve_for_primes_to(n):
    size = n//2
    sieve = [1]*size
    limit = int(n**0.5)
    for i in range(1,limit):
        if sieve[i]:
            val = 2*i+1
            tmp = ((size-1) - i)//val
            sieve[i+val::val] = [0]*tmp
    return sieve
print [2] + [i*2+1 for i, v in enumerate(sieve_for_primes_to(10000000)) 
if v and i>0]

谁能描述一下这段代码是如何工作的？

Answer 1

这称为 Sieve of Eratosthenes，wiki 页面对其进行了很好的描述。

它的要点是这样的：

你 select 个数字从 2 开始向上，然后你：

将数字select标记为质数。
从您的集合中删除该号码的所有倍数，以防止它们在将来被 select编辑。
见1)

Answer 2

这实际上是一个压缩的埃拉托色尼筛法，它不处理偶数，而是只存储和检查奇数。这就是为什么要从筛分指数得到它所做的数字 2 * i + 1。这将存储筛子所需的 space 数量减少了一半。

它不是 select 从 2 开始的数字，而是随后将 2 添加到素数列表的前面。它从 3 (2 * 1 + 1) 开始，一直到平方根。它不是使用循环来标记复合材料，而是巧妙地利用了 Python 的切片功能：

sieve[i + val::val] = [0] * tmp

将倍数设置为 0 (False)。但是，这些行似乎错误地超过了目标：

limit = int(n**0.5)
for i in range(1,limit):

因为 limit 是未压缩的值，未表示为索引，类似于：

limit = int(n ** 0.5) // 2 + 1

我的注释版本（更正？）代码：

def sieve_for_primes_to(n):
    size = n // 2  # allocate storage for odd numbers up to n
    sieve = [True] * size  # mark all odd numbers as prime to start
    limit = int(n ** 0.5) // 2 + 1  # int(sqrt(n)) as an index

    for index in range(1, limit):  # ie. number in range(3, int(sqrt(n)))
        if sieve[index]:  # if still marked as prime
            number = 2 * index + 1  # index to number conversion (1 -> 3)
            multiples = ((size - 1) - index) // number  # how many multiples from here to end of sieve
            sieve[index + number::number] = [False] * multiples  # mark odd composites/multiples False

    return sieve

print [2] + [2 * index + 1 for index, boolean in enumerate(sieve_for_primes_to(10000000)) if boolean and index > 0]

这里可能还有另外一个优化可以做：

sieve[index + number::number] = [False] * multiples

这将在当前素数的下一个奇数倍处开始标记复合倍数。但这意味着 5 从 15 开始标记，它已经被 3 标记为复合。我们实际上可以在当前素数 25 的平方处开始标记复合倍数。OP 练习，我们将如何修改此压缩表示代码以合并此优化？

了解快速素数生成器

Understand fast prime numbers generator

python

primes